В теории графов , граф пересечений является графиком , который представляет картину пересечений семейства множеств . Любой граф может быть представлен как граф пересечений, но некоторые важные специальные классы графов могут быть определены типами наборов, которые используются для их представления пересечений.
Формальное определение [ править ]
Формально граф пересечений G - это неориентированный граф, образованный семейством множеств
- S i , i = 0, 1, 2, ...
создав по одной вершине v i для каждого множества S i и соединив две вершины v i и v j ребром всякий раз, когда соответствующие два множества имеют непустое пересечение, т. е.
- E ( G ) = {{ v i , v j } | S i ∩ S j ≠ ∅}.
Все графики представляют собой графики пересечений [ править ]
Любой неориентированный граф G может быть представлена в виде графа пересечений: для каждой вершины V I из G , образуют множество S я , состоящий из ребер, инцидентных V я ; то два таких множества имеют непустое пересечение тогда и только тогда, когда соответствующие вершины имеют общее ребро. Эрдеш, Гудман и Поза (1966) предлагают более эффективную конструкцию (то есть требует меньшего общего числа элементов во всех совокупностях S i ), в которой общее количество элементов множества не превышает n 2 / 4 где n- количество вершин в графе. Они приписывают Шпильрайн-Марчевскому (1945) наблюдение, что все графы являются графами пересечений , но говорят, что видели также Чулика (1964) . Число пересечений графа - это минимальное общее количество элементов в любом представлении пересечения графа.
Классы графов пересечений [ править ]
Многие важные семейства графов можно описать как графы пересечений более ограниченных типов семейств множеств, например, множеств, полученных из некоторой геометрической конфигурации:
- Граф интервалов определяются как граф пересечений отрезков на прямом или подключенные подграфы пути графа .
- Индифферентность графы могут быть определены как граф пересечений единичных интервалов на прямом
- Дуга окружности граф определяются как граф пересечений дуг на окружности .
- Многоугольника круговая диаграмма определяется как пересечение многоугольников с углами на окружности.
- Одна характеристика хордального графа - это граф пересечений связных подграфов дерева .
- Трапециевидный график , определяются как граф пересечений трапеций , образованных из двух параллельных линий. Они являются обобщением понятия графа перестановок , в свою очередь, они являются частным случаем семейства дополнений к графам сравнимости, известного как графы кокосопарабельности.
- График диска единицы определяются как граф пересечений единичных дисков в плоскости.
- Круговая диаграмма представляет собой пересечение граф множества хорд окружности.
- Теорема об упаковке кругов утверждает, что планарные графы - это в точности графы пересечений семейств замкнутых дисков на плоскости, ограниченной непересекающимися окружностями.
- Гипотеза Шейнермана (теперь теорема) утверждает, что каждый планарный граф также может быть представлен как граф пересечений отрезков прямых на плоскости. Однако графы пересечений линейных сегментов также могут быть неплоскими, и распознавание графов пересечений линейных сегментов является полным для экзистенциальной теории действительных чисел ( Schaefer 2010 ).
- Линейный график графа G определяются как граф пересечений ребер G , где мы представляем каждое ребро в качестве множества своих два конечных точек.
- Строка граф является графом пересечений кривых на плоскости .
- Граф имеет коробчатость k, если он является графом пересечений многомерных ящиков размерности k , но не меньшей размерности.
- Клика граф является графом пересечений максимальных клик другого графа
- Блок граф из кликова дерева граф пересечений двусвязных компонентов другого графа
Шайнерман (1985) охарактеризовал классы пересечений графов , семейства конечных графов, которые можно описать как графы пересечений множеств, взятых из данного семейства множеств. Необходимо и достаточно, чтобы семья обладала следующими свойствами:
- Каждый индуцированный подграф графа в семействе также должен быть в семействе.
- Каждый граф, образованный из графа в семействе путем замены вершины кликой, также должен принадлежать семейству.
- В семействе существует бесконечная последовательность графов, каждый из которых является индуцированным подграфом следующего графа в последовательности, со свойством, что каждый граф в семействе является индуцированным подграфом графа в последовательности.
Если представления графа пересечений имеют дополнительное требование, что разные вершины должны быть представлены разными наборами, то свойство расширения клики может быть опущено.
Понятия, связанные с данным [ править ]
Порядок теоретико- аналог графов пересечений являются включение заказов . Точно так же, как представление пересечения графа помечает каждую вершину набором, так что вершины смежны тогда и только тогда, когда их множества имеют непустое пересечение, поэтому представление включения f для poset помечает каждый элемент набором так, чтобы для любого x и y в ЧУМ, x ≤ y тогда и только тогда, когда f ( x ) ⊆ f ( y ).
См. Также [ править ]
- График контактов
Ссылки [ править ]
- Чулик К. (1964), "Приложения теории графов к математической логике и лингвистике", Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963) , Прага: Publ. Дом Чехословацкой Акад. Sci., Стр. 13–20, MR 0176940.
- Эрдеш, Пол ; Гудман, AW; Posa, Луи (1966), "Представление графа множества пересечений" (PDF) , Канадский журнал математика , 18 (1): 106-112, DOI : 10,4153 / CJM-1966-014-3 , МР 0186575.
- Голумбик, Мартин Чарльз (1980), теория алгоритмических графов и совершенные графы , Academic Press, ISBN 0-12-289260-7.
- Макки, Терри А .; Макморрис, FR (1999), Темы теории графов пересечений , Монографии SIAM по дискретной математике и приложениям, 2 , Филадельфия: Общество промышленной и прикладной математики, ISBN 0-89871-430-3, Руководство по ремонту 1672910.
- Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des classes d'ensembles", Fund. Математика. , 33 : 303–307, MR 0015448.
- Шефер, Маркус (2010), «Сложность некоторых геометрических и топологических задач» (PDF) , Graph Drawing, 17-й Международный симпозиум, GS 2009, Чикаго, Иллинойс, США, сентябрь 2009 г., Revised Papers , Lecture Notes in Computer Science, 5849 , . Springer-Verlag, стр 334-344, DOI : 10.1007 / 978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
- Scheinerman, Эдвард Р. (1985), "Характеризуя классы пересечения графов", дискретная математика , 55 (2): 185-193, DOI : 10.1016 / 0012-365X (85) 90047-0 , МР 0798535.
Дальнейшее чтение [ править ]
- Для обзора теории графов пересечений и важных специальных классов графов пересечений см. McKee & McMorris (1999) .
Внешние ссылки [ править ]
- Ян Кратохвил, Видеолекция о графах пересечений (июнь 2007 г.)
- Э. Приснер, Путешествие через графство пересечений
