Факторно-критический граф
В теории графов — математической дисциплине — факторно-критический граф (или гипосопоставимый граф). [1] [2] ) — граф с n вершинами, в котором каждый индуцированный подграф из n − 1 вершин имеет идеальное паросочетание . (Идеальное паросочетание в графе — это подмножество его ребер, каждая из вершин которого является конечной точкой ровно одного из ребер в подмножестве.)
Паросочетание, охватывающее все вершины графа, кроме одной, называется почти идеальным паросочетанием . То же самое можно сказать и о факторно-критическом графе — это графе, в котором существуют почти идеальные паросочетания, избегающие всех возможных вершин.
Примеры
[ редактировать ]
нечетной длины Любой граф циклов факторкритичен, [1] как и любой полный граф с нечетным числом вершин. [3] В более общем смысле, каждый гамильтонов граф с нечетным числом вершин является факторкритичным. Графы дружбы (графы, образованные путем соединения набора треугольников в одной общей вершине) предоставляют примеры графов, которые являются факторно-критическими, но не гамильтоновыми.
Если граф G факторно-критичен, то таким же является и мицельский граф G . Например, граф Грётча , Мицельскиан пятивершинного циклического графа, фактор-критичен. [4]
Любой 2-связный граф без клешней с нечетным числом вершин факторкритичен. Например, граф с 11 вершинами, образованный удалением вершины из правильного икосаэдра (граф гировытянутой пятиугольной пирамиды ), является одновременно 2-связным и свободным от клешней, поэтому он факторкритичен. Этот результат непосредственно следует из более фундаментальной теоремы о том, что каждый связный граф без клешней с четным числом вершин имеет идеальное паросочетание. [5]
Характеристики
[ редактировать ]Критически важные для фактора графы можно охарактеризовать несколькими различными способами, кроме их определения как графов, в которых удаление каждой вершины обеспечивает идеальное совпадение:
- Тибор Галлай доказал, что граф фактор-критичен тогда и только тогда, когда он связен и для каждого узла v графа существует максимальное паросочетание , не включающее v . Из этих свойств следует, что граф должен иметь нечетное число вершин и что каждое максимальное совпадение должно соответствовать всем вершинам, кроме одной. [6]
- Ласло Ловас доказал, что граф фактор-критичен тогда и только тогда, когда он имеет разложение нечетного уха — разбиение его ребер на последовательность подграфов, каждый из которых представляет собой путь или цикл нечетной длины , первый из которых входит в последовательность будучи циклом, каждый путь в последовательности имеет обе конечные точки, но не имеет внутренних точек на вершинах в предыдущих подграфах, и каждый цикл, кроме первого в последовательности, имеет ровно одну вершину в предыдущих подграфах. Например, граф на иллюстрации может быть разделен таким образом на цикл из пяти ребер и путь из трех ребер. В случае, если также задано почти идеальное сопоставление фактор-критического графа, разложение уха можно выбрать таким образом, чтобы каждое ухо чередовало совпадающие и несовпадающие ребра. [7] [8]
- Граф также факторно-критичен тогда и только тогда, когда его можно свести к одной вершине с помощью последовательности сокращений циклов нечетной длины. Более того, в этой характеристике можно выбрать каждый цикл последовательности так, чтобы он содержал вершину, образованную сокращением предыдущего цикла. [1] Например, если сжать уши при разложении уха в порядке, заданном разложением, то в момент сокращения каждого уха оно образует нечетный цикл, поэтому характеристику разложения уха можно использовать для нахождения последовательности нечетных циклов. заключать контракт. И наоборот, из последовательности нечетных циклических сокращений, каждое из которых содержит вершину, образовавшуюся в результате предыдущего сокращения, можно сформировать декомпозицию ушей, в которой уши представляют собой наборы ребер, сжимающихся на каждом этапе.
- Предположим, что граф G дан вместе с выбором вершины v и паросочетанием M , которое покрывает все вершины, кроме v . Тогда G когда существует набор путей в G , чередующихся между совпадающими и несовпадающими ребрами, которые соединяют v с каждой из других вершин в G. фактор-критичен тогда и только тогда , На основе этого свойства можно за линейное время определить, является ли граф G с заданным почти идеальным паросочетанием факторно-критическим. [9]
Характеристики
[ редактировать ]Факторно-критические графы всегда должны иметь нечетное число вершин и должны быть 2-реберно-связными (т. е. в них не может быть мостов ). [10] Однако они не обязательно 2-вершинно связны ; графики дружбы представляют собой контрпример. Факторно-критический граф не может быть двудольным , потому что в двудольном графе с почти идеальным соответствием единственные вершины, которые можно удалить для создания идеально сопоставляемого графа, — это те, которые находятся на большей стороне двудольного разделения.
Каждый 2-связный факторно-критический граф с m ребрами имеет как минимум m различных почти идеальных паросочетаний, и, в более общем смысле, каждый фактор-критический граф с m ребрами и c блоками (2-вершинно-связные компоненты) имеет как минимум m — c + 1 различные почти идеальные паросочетания. Графы, для которых эти границы точны, могут характеризоваться наличием нечетных разложений определенной формы. [3]
Любой связный граф можно преобразовать в фактор-критический граф, сжимая достаточное количество его ребер. Минимальные можно наборы ребер, которые необходимо сжать, чтобы сделать данный граф G факторкритичным, образуют основу матроида . Этот факт подразумевает, что использовать жадный алгоритм для нахождения минимального веса набора ребер, которые нужно сжать, чтобы сделать граф фактор-критичен, за полиномиальное время . [11]
Приложения
[ редактировать ]Цветок — это факторно -критический подграф более крупного графа. Цветы играют ключевую роль в Джека Эдмондса для алгоритмах максимального соответствия и идеального соответствия минимального веса в недвудольных графах. [12]
В полиэдральной комбинаторике фактор-критические графы играют важную роль в описании граней соответствующего многогранника данного графа. [1] [2]
Обобщения и родственные концепции
[ редактировать ]Граф называется k -фактор-критическим, если каждое подмножество из n - k вершин имеет идеальное паросочетание. Согласно этому определению, гипосогласуемый граф является 1-факторным. [13] В более общем смысле, граф является ( a , b ) -фактор-критическим, если каждое подмножество из n - k вершин имеет r -фактор, то есть это множество вершин r -регулярного подграфа данного графа.
( Под критическим графом без квалификации) обычно понимают граф, для которого удаление каждой вершины уменьшает количество цветов, необходимых для раскраски графа . Понятие критичности использовалось в теории графов в более широком смысле для обозначения графов, для которых удаление каждой возможной вершины меняет или не меняет некоторые важные свойства графа. Граф , критический для сопоставления, — это граф, для которого удаление любой вершины не меняет размер максимального сопоставления ; согласно характеристике Галлаи, графы, критичные к сопоставлению, - это именно те графы, в которых каждый компонент связности факторкритичен. [14] Граф дополнений критического графа обязательно критичен к сопоставлению, и этот факт был использован Галлаем для доказательства нижних оценок числа вершин в критическом графе. [15]
Помимо теории графов, концепция факторной критичности была распространена на матроиды путем определения типа ушной декомпозиции на матроидах и определения матроида как факторно-критического, если он имеет ушное разложение, в котором все уши нечетны. [16]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с д Пулибланк, Западная Каролина ; Эдмондс, Дж. (1974), «Грани 1-совпадающих многогранников», в Берге, К .; Рэй-Чаудхури, Д.К. (ред.), Семинар по гиперграфу , Конспекты лекций по математике, том. 411, Springer-Verlag, стр. 214–242, номер документа : 10.1007/BFb0066196 , ISBN. 978-3-540-06846-4 .
- ^ Jump up to: Перейти обратно: а б Корнюжоль, Г. ; Pulleyblank, WR (1983), «Критические графы, паросочетания и обходы или иерархия релаксаций для задачи коммивояжера», Combinatorica , 3 (1): 35–52, doi : 10.1007/BF02579340 , MR 0716420 , S2CID 35825797 .
- ^ Jump up to: Перейти обратно: а б Лю, Ян; Хао, Цзянсю (2002), «Перечисление почти идеальных паросочетаний факторно-критических графов», Discrete Mathematics , 243 (1–3): 259–266, doi : 10.1016/S0012-365X(01)00204-7 , МР 1874747 .
- ^ Дошлич, Томислав (2005), «Мицельскианы и паросочетания» , Discionses Mathematicae Graph Theory , 25 (3): 261–266, doi : 10.7151/dmgt.1279 , MR 2232992 .
- ^ Фаварон, Одиль ; Фландрин, Эвелин; Рыячек, Зденек (1997), «Факторная критичность и расширение соответствия в DCT-графах» , Дискуссии Mathematicae Graph Theory , 17 (2): 271–278, CiteSeerX 10.1.1.25.6314 , doi : 10.7151/dmgt.1054 , MR 1627955 .
- ^ Галлай, Т. (1963), «Neuer Beweis eines Tutte'schen Satzes», Magyar Tud. Есть. Мэтт. Исследования Int. , 8 : 135–139, МР 0166777 . Как цитирует Франк, Андраш ; Сегё, Ласло (2002), «Примечание к формуле сопоставления путей» (PDF) , Journal of Graph Theory , 41 (2): 110–119, CiteSeerX 10.1.1.20.7918 , doi : 10.1002/jgt.10055 , MR 1926313 , S2CID 206076722 .
- ^ Ловас, Л. (1972), «Заметки о факторно-критических графах», Studia Sci. Математика. Венгрия. , 7 : 279–280, МР 0335371 .
- ^ Корте, Бернхард Х .; Виген, Йенс (2008), «10.4 Ушная декомпозиция факторно-критических графов», Комбинаторная оптимизация: теория и алгоритмы , Алгоритмы и комбинаторика, том. 21 (4-е изд.), Springer-Verlag, стр. 235–241, ISBN. 978-3-540-71843-7 .
- ^ Лу, Динцзюнь; Рао, Дуннин (2004), «Характеристика факторных критических графов и алгоритм» (PDF) , Австралазийский журнал комбинаторики , 30 : 51–56, MR 2080453 .
- ^ Зейффарт, Карен (1993), «Упаковки и двойные покрытия совершенных путей максимальных планарных графов», Discrete Mathematics , 117 (1–3): 183–195, doi : 10.1016/0012-365X(93)90334-P , MR 1226141 .
- ^ Сигети, Золтан (1996), «О матроиде, определяемом ушным разложением графов», Combinatorica , 16 (2): 233–241, doi : 10.1007/BF01844849 , MR 1401896 , S2CID 206806006 . Более ранний алгоритм сокращения минимального числа (невзвешенных) ребер для достижения факторно-критического графа см. Франк, Андраш (1993), «Консервативное взвешивание и ушное разложение графов», Combinatorica , 13 (1): 65–81, doi : 10.1007/BF01202790 , MR 1221177 , S2CID 10857300 .
- ^ Эдмондс, Джек (1965), «Пути, деревья и цветы», Canadian Journal of Mathematics , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , MR 0177907 , S2CID 18909734 .
- ^ Фаварон, Одиль (1996), «О k графах, критических по -фактору» , Дискуссии Mathematicae Graph Theory , 16 (1): 41–51, doi : 10.7151/dmgt.1022 , MR 1429805 .
- ^ Эрдеш, П .; Фюреди, З. ; Гулд, Р.Дж .; Гундерсон, Д.С. (1995), «Экстремальные графы для пересекающихся треугольников» , Журнал комбинаторной теории , серия B, 64 (1): 89–100, doi : 10.1006/jctb.1995.1026 , MR 1328293 .
- ^ Галлай, Т. (1963b), «Критище Графен II», Опубл. Математика. Инст. Венгрия. акад. наук. , 8 : 373–395 . Как цитирует Стелик, Матей (2003), «Критические графы со связными дополнениями», Журнал комбинаторной теории , серия B, 89 (2): 189–194, номер документа : 10.1016/S0095-8956(03)00069-8 , MR 2017723 .
- ^ Сегеди, Балаж ; Сегеди, Кристиан (2006), «Симплектические пространства и ушное разложение матроидов», Combinatorica , 26 (3): 353–377, doi : 10.1007/s00493-006-0020-3 , MR 2246153 , S2CID 11578490 .