СПЕКТР РЕБЕРНЫХ РАЗРЕЗОВ ГРАФА И ЗАДАЧА ИЗОМОРФИЗМА
Journal Title: Вісник Запорізького національного університету. Фізико-математичні науки - Year 2017, Vol 1, Issue
Abstract
Данная работа посвящена одной из основополагающих структур в графе – реберному разрезу графа. В статье приведены формальные определения центрального и реберного разрезов графа. Показана связь между центральными разрезами и квалиразрезами в графе. На основании понятия реберного разреза и операции порождения строится спектр реберных разрезов, характеризующийся множеством ребер определенного уровня. Показано, что спектр реберных разрезов графа может быть применен для задачи распознавания изоморфизма графов.
Authors and Affiliations
С. В. Курапов, М. В. Давидовский
Keywords
Related Articles
- EP ID EP457697
- DOI -
- Views 76
- Downloads 0
АНАЛИТИЧЕСКОЕ И ПРИБЛИЖЕННО АНАЛИТИЧЕСКОЕ РЕШЕНИЕ ПЛОСКОЙ КОНТАКТНОЙ ЗАДАЧИ С УЧЕТОМ ТРЕНИЯ И ШЕРОХОВАТОСТИ
Рассматривается плоская квазистатическая задача о скольжении с трением штампа с плоским основанием по поверхности упругого шероховатого слоя при линейном законе деформирования шероховатости. Предполагается отсутствие нак...
ЯЗЫК ОПИСАНИЯ ТВЕРДОТЕЛЬНЫХ ГЕОМЕТРИЧЕСКИХ МОДЕЛЕЙ FORTU-F
Предложен проблемно-ориентированный язык спецификаций (формального описания моделей) FORTU-F, позволяющий полно, непротиворечиво и однозначно описывать математические модели двух- и трехмерных геометрических областей про...
ФІЗИЧНІ МЕТОДИ ДОСЛІДЖЕННЯ КРОВІ: СУЧАСНИЙ СТАН І ПЕРСПЕКТИВИ
Проведено літературний аналіз інноваційних фізичних методів гематологічних досліджень, що використовуються або знаходяться на стадії впровадження в сучасну клінічну практику. Розглянуто основні напрямки сучасних тенденці...
ИНТЕГРА-ОПЕРАТОРНОЕ ИССЛЕДОВАНИЕ КРАЕВЫХ ПЕРИОДИЧЕСКИХ ЗАДАЧ
Исследуются краевые периодические задачи для линейного и квазилинейного уравнений гиперболического типа, используя аналитические методы. Построен оператор, переводящий класс 2π-периодических функций в себя. Установлены о...
КОЛЕБАНИЯ ПРЯМОУГОЛЬНОЙ ПЛАСТИНЫ, РАЗДЕЛЯЮЩЕЙ ИДЕАЛЬНЫЕ ЖИДКОСТИ РАЗНОЙ ПЛОТНОСТИ В ПРЯМОУГОЛЬНОМ КАНАЛЕ С УПРУГИМИ ОСНОВАНИЯМИ
Выведено частотное уравнение собственных колебаний упругой пластины, горизонтально разделяющей идеальные жидкости разной плотности в прямоугольном канале с упругими основаниями в виде прямоугольных пластин. Рассмотрены п...