ЗАВИСИМОСТЬ МЕЖДУ ПЕСОЧНОЙ ГРУППОЙ ГРАФА И ЕГО МАТРОИДОМ

Постановка проблемы: определение структуры песочных групп графов представляет собой сложную вычис- лительную задачу. В попытке снизить сложность решения данной задачи для некоторых классов графов была обна- ружена зависимость между песочной группой графа и его матроидом: структура песочной группы графа зависит только от его матроида. Целью статьи является доказательство данного утверждения. Методы: для доказательства изоморфности песочных групп 2-изоморфных графов были использованы элементарные операции с матрица- ми Лапласа этих графов. Основной результат статьи получен как следствие теоремы Уитни о 2-изоморфных графах. Результаты: доказано, что структура песочной группы графа полностью определяется структурой матроида этого графа.

Авторы

И. А. Крепкий

Тэги

песочные группы графы матроиды нормальная форма Смита 2-изоморфные графы.

Тематические рубрики

Предметные рубрики

В этом же номере:

ОБ АЛГОРИТМЕ ПРИНЯТИЯ РЕШЕНИЙ: ОТ АРХИТЕКТУРЫ РЕГИОНАЛЬНОЙ АВИАСЕТИ К ОПЦИОНАЛЬНОСТИ САМОЛЕТОВ (НА ПРИМЕРЕ КРАСНОЯРСКОГО КРАЯ), УПРАВЛЕНИЕ КОМБИНИРОВАННЫМ ВЫВОДОМ В ДИСКРЕТНЫХ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ, ...

Резюме по документу**

В попытке снизить сложность решения данной задачи для некоторых классов графов была обнаружена зависимость между песочной группой графа и его матроидом: структура песочной группы графа зависит только от его матроида. <...> Методы: для доказательства изоморфности песочных групп 2-изоморфных графов были использованы элементарные операции с матрицами Лапласа этих графов. <...> Ключевые слова — песочные группы, графы, матроиды, нормальная форма Смита, 2-изоморфные графы. <...> Песочная группа связного графа представляет собой подмножество множества так называемых редуцированных песочных куч графа (песочная куча — отображение из множества вершин графа в множество неотрицательных чисел), снабженным операцией сложения куч (сложение — поточечное суммирование песочных куч с последующим редуцированием результата при помощи процедуры, определяемой конструкцией графа). <...> В песочную группу входят только так называемые рекуррентные песочные кучи, удовлетворяющие burning test [3]. <...> Также известно, что песочная группа связного планарного графа изоморфна песочной группе графа, дуального данному [6]. <...> Например, группы, изоморфные песочным группам, возникают в связи с вопросами замощения прямоугольной доски фигурами домино [9]. <...> [10] была установлена связь между некоторыми группами действий на множествах непериодических двухцветных ожерелий и песочными группами графов де Бройна. <...> ИНФОРМАЦИОННОУПРАВЛЯЮЩИЕ СИСТЕМЫ 23 Постановка проблемы: определение структуры песочных групп графов представляет собой сложную вычис ТЕОРЕТИЧЕСКАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА Определение 1. <...> Матрица M называется нормальной формой Смита матрицы M [11]. <...> Будем обозначать как M мультимножество диагональных элементов нормальной формы Смита матрицы M. <...> Пусть n вершин мультиграфа G пронумерованы от 1 до n. <...> Матрица M называется матрицей Лапласа графа G. <...> Мы будем использовать (как в работе [12]) определение песочной группы мультиграфа, построенное в терминах нормальной <...>

** - вычисляется автоматически, возможны погрешности

Похожие документы:

Похожие документы из РУАЭСТ
|
Похожие документы из Руконт

ЗАВИСИМОСТЬ МЕЖДУ ПЕСОЧНОЙ ГРУППОЙ ГРАФА И ЕГО МАТРОИДОМ

Помощь:

Участники: