Некоторые сведения из теории графов - Алгоритмы нескольких махов

Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6].

Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это непустое множество вершин или узлов, а E -- множество пар (в случае неориентированного графа -- неупорядоченных) вершин, называемых ребрами.

Вершины и ребра графа называются также элементами графа, число вершин в графе |V| -- порядком, число ребер |E| -- размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e={u, v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Маршрутом в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. Цепью называется маршрут без повторяющихся ребер. Простой цепью называется маршрут без повторяющихся вершин (откуда следует, что в простой цепи нет повторяющихся ребер).

Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его ребер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u, v, u) является циклом. Чтобы избежать таких "вырожденных" случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нем не повторяются; элементарным, если он простой и вершины в нем не повторяются.

Кликой неориентированного графа называется подмножество его вершин, таких, что любые две вершины подмножества соединены ребром.

Максимальная клика - это клика, которая не может быть расширена путем включения дополнительных смежных вершин, то есть нет клики большего размера, включающей все вершины данной клики.

Граф называется хордальным, если каждый из его циклов, имеющий четыре и более дуг, имеет хорду, которая является ребром, соединяющим две вершины, не смежные в цикле. Эквивалентное определение -- если любой цикл без хорд имеет максимум три ребра.

Совершенный порядок исключения в графе -- это порядок вершин графа, такой что для каждой вершины v, v и соседи v, находящиеся после v в упорядочении, образуют клику. Граф хордален тогда и только тогда, когда имеет совершенный порядок исключения.

Астероидальной тройкой (АТ) называются три вершины графа, что каждая пара таких вершин соединяется путем, не проходящим через замкнутую окрестность третьей вершины.

Теорема 1. Граф интервальный тогда и только тогда, когда он хордален и не содержит астероидальных троек [10].

Четыре вершины графа порождают клешню с центром в вершине, если - три попарно несмежных соседа вершины.

Теорема 2. Интервальный граф является единичным интервальным тогда и только тогда, когда он не содержит порожденных клешней [11].

Единичный интервальный граф -- граф пересечений интервалов одинаковой длины.

Пусть граф с вершинами и порядок (последовательность) вершин. Порядок называется I-порядком графа, если для всех и, выполняется для всех. Порядок называется UI-порядком графа если для всех.

Теорема 3. Граф интервальный тогда и только тогда, когда у него имеется I-порядок [12].

Теорема 4. Граф единичный интервальный тогда и только тогда, когда у него имеется UI-порядок [13].

Примеры некоторых различных типов графов:

Хордальный, не являющийся интервальным. (bdf астероидальная тройка - есть пути соединяющие каждую пару, не проходящие через закрытое множество соседей, Рис.2).

Рис.2

Интервальный, не являющийся единичным интервальным (клешня, попарно несмежные соседи - не соединяются ребрами, Рис.3).

Рис.3

Единичный интервальный (самый простой пример, Рис.4)

Рис.4

Похожие статьи




Некоторые сведения из теории графов - Алгоритмы нескольких махов

Предыдущая | Следующая