Введение к работе
Актуальность темы. Теория графов является одним из важнейших и интереснейших разделов математики. В различных областях математики — алгебре, топологии, информатике и других — возникает потребность описания свойств тех или иных объектов па языке теории графой и использования результатов теории графов, что подчеркивает значимость изучения графов и их свойств.
Одним из основных понятий в теории графов является понятие связности. Граф называется связным, если между любыми двумя его вершинами существует путь. Граф называется (вершинно) к-связным, если в нем не менее к + 1 вершин и при удалении любых к — 1 вершин получается связный граф. Понятие вершинной k-связности является обобщением понятия связности и по этой причине имеет большое теоретическое и практическое значение.
Одно из направлений исследований по вершинной связности это исследование структуры разбиения k-связных графов к-разделяющими множествами (то есть к-вершинными множествами, удаление которых делает граф несвязным). Интерес к этому объясняется тем, что в изучении свойств связных графов важную роль играет структура разбиения графа точками сочленения — вершинами, удаление которых делает этот граф несвязным. Точки сочленения разбивают граф на блоки максимальные по включению двусвязные подграфы, структуру этого разбиения удобно отображать с помощью дерева блоков и точек сочленения.
Многими исследователями делались попьаки обобщить эти конструкции на разбиение k-связного графа его к-разделяющими множествами. В 1966 году W. Т. Tutte подробно описал конструкцию разбиения двусвязного графа его 2-разделяютцими множествами. Эга структура является естественным обобщением структуры блоков и точек сочленения для двусвязного графа и также отображается с помощью дерева. В 1992 году W. Hohberg предложил обобщен иг ->\vV\ киш і mvk тім и а случай
разбиения fc-связного графа его fc-разделяющими множествами для произвольного к. Основным недостатком конструкции, которую предложил W. Hohbcrg. является зависимость получаемых и результате блоков от процесса разбиения и, как следствие, отсутствие единственности структуры разбиения.
F. Harary, Y. Kodaina (1964) и D. W. Matula (1978) предлагали называть fc-блоком или k-компонентой графа G максимальный по включению fc-связный подграф этого графа. При очевидной аналогии в определении с блоками связного графа, свойства вводимых таким образом fc-блоков имеют мало аналогий со свойствами классических двусвязных блоков.
Таким образом, вопрос об изучении структуры разбиения fc-снязного графа его k-разделяющими множествами является актуальным.
Цели работы. Основные цели диссертации — разработать новый подход к описанию структуры разбиения fc-связного графа ею k-разделяющими множествами, дающий однозначно определенную конструкцию частей разбиения для произвольного fc-связного графа, и изучить свойства k-разделяющих множеств и частей разбиения графа наборами таких множеств.
Общая методика работы. В работе использовались классические методы работы с fc-связными графами и новые идеи. Одной из наиболее существенных новых методик изучения структуры разбиения fc-связного графа является описанная в третьей главе диссертации теория ромашек.
Основные результаты работы. 1. Разработан новый подход к описанию структуры разбиения fc-связного графа его k-разделяющим и множествами, дающий однозначно определенную конструкцию частей разбиения для произвольного fc-связного графа.
2. Для произвольного набора б, состоящего из k-разделяющих множеств fc-связного графа G, рассматривается граф зависимости D(&),
вершины которого соответствуют множествам набора & и две вершины смежны тогда и только тогда, когда соответствующие множества зависимы, то есть разделяют друг друга. Набор & разбивается на компоненты зависимости — поднаборы, соответсвующие компонентам связности графа зависимости D(&). Доказано, что существует дерево компонент зависимости G& вершины которого соответствуют частям разбиения графа G набором (5 и компонентам зависимости набора &, причем каждая часть А разбиения графа G набором 6 является частью разбиения графа G набором из множеств, входящих только в те компоненты зависимости набора &, которые смежны части Л в дереве G&-
3. Разработана новая методика изучения структуры разбиения
k-связного графа теория ромашек. Изучение разбиения к;-связного
графа произвольным набором к-разделяющих множеств сводится к из
учению разбиения этого графа набором, образующим ромашку (разбие
ние графа таким набором имеет достаточно простую циклическую струк
туру)- Доказано, что каждая часть разбиения fc-связиого графа G набо
ром fc-разделяющих множеств & содержит хотя бы к вершин тогда и
только тогда, когда каждая компонента зависимости набора 6 образует
ромашку. На языке теории ромашек дано описание структуры разбиения
двусвязного графа произвольным набором его 2-разделяющих множеств.
4. С помощью теории ромашек дано детальное описание структуры
fc-разделяющих множеств в слабо нерасщепимом k-связном графе.
Научная новизна. Все основные результаты диссертации являются новыми.
Практическая и теоретическая ценность. Работа носит теоретический характер. Результаты работы могут быть использованы для дальнейшего изучения свойств k-связных графов. В частности, теория ромашек может оказаться полезна для решения различных вопросов, связанных с изучением А;-связных графов. Детальное описание структуры fc-разделяющих множеств в слабо перасщепимых fc -связных графах от-
крываег перспективы для изучения свойств графов этого класса.
Апробация работы. Результаты диссертации докладывались на семинаре по дискретной матемашке ПОМИ РАН и на Восьмом Международном семинаре "Дискретная математика и ее приложения" (Москва, МГУ, 2004).
Публикации. Основные результаты диссертации изложены в работах [2, 3, 4], перечисленных в конце автореферата.
Структура и объем диссертации. Диссертация состоит из введения
и пяти глав. Нумерация разделов, формул, замечаний, лемм и теорем ведется отдельно для каждой главы, нумерация определений — сквозная. Текст диссертации изложен на 135 страницах (исключая список литературы). Список литературы содержит 32 наименования.
