Из Википедии, бесплатной энциклопедии
  (Перенаправлен из переходной ориентации )
Перейти к навигации Перейти к поиску

В теории графов , A сопоставимость график представляет собой неориентированный граф , который соединяет пары элементов, которые сравнимы друг с другом в частичном порядке . Сопоставимость графики также называют транзитивно ориентируемых графики , частично упорядочиваема графики , удерживающие графики , [1] и графы делителей . [2] граф несравнимости является неориентированный граф , который соединяет пары элементов, которые не сопоставимы друг с другом в частичном порядке .

Определения и характеристика [ править ]

Диаграмма Хассе чугуна (слева) и его граф сопоставимости (справа)
Один из запрещенных индуцированных подграфов графа сравнимости. Обобщенный цикл a - b - d - f - d - c - e - c - b - a в этом графе имеет нечетную длину (девять), но не имеет треугольных хорд.

Для любого строго частично упорядоченного множества ( S , <) граф сравнимости ( S , <) - это граф ( S , ⊥), вершины которого являются элементами S, а ребра - те пары { u , v } из элементы такие, что u < v . То есть для частично упорядоченного множества возьмите ориентированный ациклический граф , примените транзитивное замыкание и удалите ориентацию.

Эквивалентно, сопоставимость представляет собой граф , который имеет переходную ориентацию , [3] задание направлений для ребер графа (т.е. ориентации графа) таким образом, что отношение смежности полученного ориентированного графа является транзитивным : всякий раз , когда существует существуют направленные ребра ( x , y ) и ( y , z ), должно существовать ребро ( x , z ).

Любой конечный частичный порядок можно представить как семейство множеств, такое что x < y в частичном порядке, всякий раз, когда набор, соответствующий x, является подмножеством множества, соответствующего y . Таким образом можно показать, что графы сопоставимости эквивалентны графам включения семейств множеств; то есть граф с вершиной для каждого набора в семействе и ребром между двумя наборами, если одно из них является подмножеством другого. [4] В качестве альтернативы, можно представить частичный порядок семейством целых чисел , так что x < y, если целое число, соответствующее x, является делителемцелого числа, соответствующего y . Из-за этой конструкции графы сравнимости также называются графами делителей. [2]

Графы сопоставимости можно охарактеризовать как графы, такие, что для каждого обобщенного цикла нечетной длины можно найти ребро ( x , y ), соединяющее две вершины, которые находятся на расстоянии два в цикле. Такое ребро называется треугольной хордой . В этом контексте обобщенный цикл определяется как закрытый обход , при котором каждое ребро графа используется не более одного раза в каждом направлении. [5] Графы сопоставимости также могут быть охарактеризованы списком запрещенных индуцированных подграфов . [6]

Связь с другими семействами графов [ править ]

Каждый полный график - это график сопоставимости, график сопоставимости общего порядка . Все ациклические ориентации полного графа транзитивны. Каждый двудольный граф также является графом сравнимости. Ориентация ребер двудольного графа от одной стороны двудольного графа к другой приводит к транзитивной ориентации, соответствующей частичному порядку высоты два. Как отмечает Сеймур (2006) , каждый граф сравнимости, который не является ни полным, ни двудольным, имеет косое разбиение .

Дополнением любого графа интервалов является сопоставимость граф. Отношение сопоставимости называется интервальным порядком . Графы интервалов - это именно те графы, которые являются хордовыми и имеют дополнения к графам сопоставимости. [7]

Граф перестановки является сдерживание граф на множестве интервалов. [8] Следовательно, графы перестановок являются еще одним подклассом графов сопоставимости.

В тривиальном совершенных графах являются сопоставимость графикой корневых дерев . [9] Кографы можно охарактеризовать как графы сравнимости последовательно-параллельных частичных порядков ; таким образом, кографы также являются графами сопоставимости. [10]

Графики пороговых значений - еще один особый вид графов сопоставимости.

Каждый график сопоставимости идеален . Совершенство графов сравнимости - это теорема Мирского , а совершенство их дополнений - теорема Дилворта ; эти факты вместе с теоремой об идеальном графе могут быть использованы для доказательства теоремы Дилворта из теоремы Мирского или наоборот. [11] В частности, графы сопоставимости - это идеально упорядочиваемые графы , подкласс идеальных графов: алгоритм жадной раскраски для топологического упорядочения транзитивной ориентации графа раскрасит их оптимально. [12]

Дополнение каждого сравнимости графа является строка графа . [13]

Алгоритмы [ править ]

Транзитивная ориентация графа, если она существует, может быть найдена за линейное время. [14] Однако алгоритм для этого будет назначать ориентацию ребрам любого графа, поэтому для выполнения задачи проверки того, является ли граф графом сопоставимости, необходимо проверить, является ли полученная ориентация транзитивной, что доказуемо эквивалентно в сложность умножения матриц .

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

Заметки [ править ]

  1. ^ Golumbic (1980) , стр. 105; Brandstädt, Le & Spinrad (1999) , стр. 94.
  2. ^ а б Chartrand et al. (2001) .
  3. ^ Ghouila-Хури (1962) ; см. Brandstädt, Le & Spinrad (1999) , теорема 1.4.1, стр. 12. Хотя ориентации, исходящие из частичных порядков, являются ациклическими , нет необходимости включать ацикличность как условие этой характеристики.
  4. ^ Уррутия (1989) ; Троттер (1992) ; Brandstädt, Le & Spinrad (1999) , раздел 6.3, стр. 94–96.
  5. ^ Ghouila-Хури (1962) и Гилмор & Хоффман (1964) . См. Также Brandstädt, Le & Spinrad (1999) , теорема 6.1.1, стр. 91.
  6. ^ Галлай (1967) ; Троттер (1992) ; Brandstädt, Le & Spinrad (1999) , стр. 91 и стр. 112.
  7. ^ Транзитивная ориентируемость дополнений интервальных графов была доказана Гуила-Хури (1962) ; характеристика интервальных графов дана Гилмором и Хоффманом (1964) . См. Также Golumbic (1980) , проп. 1.3. С. 15–16.
  8. ^ Dushnik & Miller (1941) . Brandstädt, Le & Spinrad (1999) , теорема 6.3.1, с. 95.
  9. ^ Brandstädt, Le & Спинрад (1999) , теорема 6.6.1, стр. 99.
  10. ^ Brandstädt, Le & Спинрад (1999) , следствие 6.4.1, стр. 96; Юнг (1978) .
  11. ^ Golumbic (1980) , теоремы 5.34 и 5.35, стр. 133.
  12. ^ Maffray (2003) .
  13. ^ Golumbic, Rotem и Уррутиа (1983) и Lovász (1983) . См. Также Fox & Pach (2012) .
  14. ^ МакКоннелл и Спинрад (1997) ; см. Brandstädt, Le & Spinrad (1999) , стр. 91.

Ссылки [ править ]

  • Брандштадт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
  • Чартран, Гэри ; Мунтян, Ралука; Саенфольфат, Варапорн; Чжан, Пинг (2001), «Какие графы являются графами делителей?», Труды Тридцать второй Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Лос-Анджелес, 2001), Congressus Numerantium , 151 : 189–200, MR  1887439
  • Душник, Бен; Миллер, EW (1941), "Частично упорядоченные множества", Американский журнал математики , Университет Джона Хопкинса Press, 63 (3): 600-610, DOI : 10,2307 / 2371374 , ЛВП : 10338.dmlcz / 100377 , JSTOR  2371374 , MR  0004862.
  • Fox, J .; Пач, Дж. (2012), «Строковые графы и графы несравнимости» (PDF) , Успехи в математике , 230 (3): 1381–1401, DOI : 10.1016 / j.aim.2012.03.011.
  • Галлай, Тибор (1967), "Transitiv orientierbare Graphen", Acta Math. Акад. Sci. Подвешенный. , 18 (1-2): 25-66, DOI : 10.1007 / BF02020961 , МР  0221974 , S2CID  119485995.
  • Гуила-Ури, Ален (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une Relations d'ordre", Les Comptes rendus de l'Académie des Sciences , 254 : 1370– 1371, Руководство по ремонту  0172275.
  • Гилмор, ПК; Хоффман, AJ (1964), "Характеристика сопоставимости графов и графов интервалов", Canadian Journal математики , 16 : 539-548, DOI : 10,4153 / CJM-1964-055-5 , МР  0175811.
  • Голумбик, Мартин Чарльз (1980), теория алгоритмических графов и совершенные графы , Academic Press, ISBN 0-12-289260-7.
  • Golumbic, M .; Rotem, D .; Уррутия, Дж. (1983), «Графы сопоставимости и графы пересечений», Дискретная математика , 43 (1): 37–46, DOI : 10.1016 / 0012-365X (83) 90019-5.
  • Юнг, HA (1978), «Об одном классе множеств и соответствующих графах сопоставимости», Журнал комбинаторной теории, серия B , 24 (2): 125–133, DOI : 10.1016 / 0095-8956 (78) 90013-8 , MR  0491356.
  • Ловас, Л. (1983), «Совершенные графы», Избранные темы теории графов , 2 , Лондон: Academic Press, стр. 55–87..
  • Маффре, Фредерик (2003), «О раскраске совершенных графов», в Риде, Брюс А .; Продажи, Клаудия Л. (ред.), Последние достижения в области алгоритмов и комбинаторики , CMS Books in Mathematics, 11 , Springer-Verlag, pp. 65–84, doi : 10.1007 / 0-387-22444-0_3.
  • МакКоннелл, РМ; Спинрад, Дж. (1997), "Линейно-временная транзитивная ориентация", 8-й симпозиум ACM-SIAM по дискретным алгоритмам , стр. 19–25..
  • Сеймур, Пол (2006), «Как было найдено доказательство сильной гипотезы о совершенном графе» (PDF) , Gazette des Mathématiciens (109): 69–83, MR  2245898.
  • Троттер, Уильям Т. (1992), Комбинаторика и частично упорядоченные множества - теория размерностей , Johns Hopkins University Press.
  • Уррутия, Хорхе (1989), Соперник, И. (ред.), Частичные порядки и евклидова геометрия , Kluwer Academic Publishers, стр. 327–436..