Посет заболеваемости
В математике ЧУИ инцидентности или порядок инцидентности — это тип частично упорядоченного набора , который представляет отношение инцидентности между вершинами и ребрами неориентированного графа . ЧУ-множество инцидентности графа G имеет элемент для каждой вершины или ребра в G ; в этом частично упорядоченном множестве существует отношение порядка x ≤ y тогда и только тогда, когда либо x = y , либо x — вершина, y — ребро, а x — конечная точка y .
Пример
[ редактировать ]Например, зигзагообразное ЧУ-множество или ограждение с нечетным числом элементов, с чередующимися отношениями порядка a < b > c < d ... является ЧУ-множеством инцидентности графа путей .
Характеристики
[ редактировать ]Каждое ЧУИ инцидентности непустого графа имеет высоту два. Его ширина равна количеству ребер плюс количеству компонентов ациклической связности.
Частные наборы инцидентности были особенно изучены в отношении их размерности порядка и ее связи со свойствами основного графа. ЧУ-множество инцидентности связного графа G имеет порядковую размерность не более двух тогда и только тогда, когда G является графом путей, и имеет порядковую размерность не более трех тогда и только тогда, когда G не более чем планарен ( теорема Шнайдера ). [1] Однако графы, ЧУИ инцидентности которых имеют размерность порядка 4, могут быть плотными. [2] и может иметь неограниченное хроматическое число . [3] Каждый полный граф на n вершинах и, как следствие, каждый граф на n вершинах имеет ЧУ-множество инцидентности с порядковой размерностью O (log log n ). [4] Если ЧУИ инцидентности имеет высокую размерность, то он должен содержать копии ЧУИ инцидентности всех маленьких деревьев либо как подпорядки, либо как двойники подпорядков. [5]
Ссылки
[ редактировать ]- ^ Шнайдер, В. (1989), «Плоские графы и размерность частичного множества», Order , 5 (4): 323–343, doi : 10.1007/BF00353652 , S2CID 122785359 .
- ^ Агнарссон, Гейр; Фельснер, Стефан; Троттер, Уильям Т. (1999), «Максимальное количество ребер в графе ограниченной размерности с приложениями к теории колец», Discrete Mathematics , 201 (1–3): 5–19, doi : 10.1016/S0012-365X (98)00309-4 , МР 1687854 .
- ^ Троттер, Уильям Т.; Ван, Жуйдун (2014), «Наборы заболеваемости и графы покрытия», Order , 31 (2): 279–287, arXiv : 1308.2471 , doi : 10.1007/s11083-013-9301-9 , S2CID 17560524 .
- ^ Хоштен, Серкан; Моррис, Уолтер Д. младший (1999), «Порядковая размерность полного графа», Discrete Mathematics , 201 (1–3): 133–139, doi : 10.1016/S0012-365X(98)00315-X , MR 1687882 .
- ^ Брайтвелл, Грэм Р.; Троттер, Уильям Т. (1994), «Популяции заболеваемости деревьев в частично-множествах большой размерности», Order , 11 (2): 159–167, doi : 10.1007/BF01108600 , MR 1302404 , S2CID 120777046 .