Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Факторно-критический граф вместе с идеальным паросочетанием подграфов, образованный удалением одной из его вершин.

В теории графов , математической дисциплине, фактор-критический граф (или гипоматричный граф [1] [2] ) - это граф с n вершинами, в котором каждый подграф из n - 1 вершин имеет идеальное соответствие . (Идеальное соответствие в графе - это подмножество его ребер, каждая из вершин которого является конечной точкой ровно одного из ребер в подмножестве.)

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

Примеры [ править ]

Три графа дружбы , примеры негамильтоновых фактор-критических графов
Gyroelongated пятиугольная пирамида , А зубчатый свободный график , фактор-критического

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

Если граф G является фактор-критическим, то и мыцельскиан из G . Например, граф Грёча , микельскиан пятивершинного графа -цикла, фактор-критичен. [4]

Каждый 2-вершинно-связный граф без клешней с нечетным числом вершин фактор-критичен. Например, граф с 11 вершинами, образованный удалением вершины из правильного икосаэдра (граф гиродлинной пятиугольной пирамиды ), является двухсвязным и не имеет когтей, поэтому он фактор-критичен. Этот результат следует непосредственно из более фундаментальной теоремы о том, что каждый связный граф без клешней с четным числом вершин имеет полное соответствие. [5]

Характеристики [ править ]

Факторно-критические графы могут быть охарактеризованы несколькими различными способами, помимо их определения как графов, в которых удаление каждой вершины обеспечивает идеальное соответствие:

  • Тибор Галлаи доказал, что граф является фактор-критичным тогда и только тогда, когда он связан, и для каждого узла v графа существует максимальное соответствие, которое не включает v . Из этих свойств следует, что граф должен иметь нечетное количество вершин и что каждое максимальное совпадение должно соответствовать всем вершинам, кроме одной. [6]
  • Ласло Ловас доказал, что граф является фактор-критическим тогда и только тогда, когда он имеет разложение нечетного уха , разбиение его ребер на последовательность подграфов, каждый из которых является путем или циклом нечетной длины., причем первый в последовательности является циклом, причем каждый путь в последовательности имеет обе конечные точки, но не имеет внутренних точек на вершинах в предыдущих подграфах, и каждый цикл, отличный от первого в последовательности, имеет ровно одну вершину в предыдущих подграфах. Например, граф на иллюстрации может быть разбит таким образом на цикл из пяти ребер и путь из трех ребер. В случае, если также дано почти идеальное совпадение критического для факторов графа, разложение уха может быть выбрано таким образом, что каждое ухо чередуется между согласованными и несовпадающими краями. [7] [8]
  • Граф также фактор-критичен тогда и только тогда, когда он может быть сведен к одной вершине последовательностью сокращений циклов нечетной длины. Более того, в этой характеристике можно выбрать каждый цикл в последовательности так, чтобы он содержал вершину, образованную сжатием предыдущего цикла. [1] Например, если сжимать уши разложения уха в порядке, заданном разложением, то в момент сокращения каждого уха он образует нечетный цикл, поэтому характеристика разложения уха может использоваться для поиска последовательности нечетных циклов для сокращения. И наоборот, из последовательности нечетных сокращений цикла, каждое из которых содержит вершину, образованную в результате предыдущего сокращения, можно сформировать декомпозицию ушей, в которой уши представляют собой наборы ребер, сокращаемых на каждом шаге.
  • Предположим, что граф G задан вместе с выбором вершины v и паросочетания M, которое покрывает все вершины, кроме v . Тогда G является фактор-критическим тогда и только тогда , когда существует множество путей в G , чередующихся между согласованными и несогласованных краями, которые соединяют против каждого из остальных вершин в 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]

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

  1. ^ a b c d Pulleyblank, WR ; Эдмондс, Дж. (1974), «Грани 1-согласованных многогранников», в Берге, К .; Ray-Chaudhuri, DK (ред.), Hypergraph Seminar , Lecture Notes in Mathematics, 411 , Springer-Verlag, pp. 214–242, doi : 10.1007 / BFb0066196 , ISBN 978-3-540-06846-4.
  2. ^ а б Cornuéjols, G .; Pulleyblank, WR (1983), «Критические графы, сопоставления и туры или иерархия релаксации для задачи коммивояжера», Combinatorica , 3 (1): 35–52, doi : 10.1007 / BF02579340 , MR 0716420 .
  3. ^ а б Лю, Ян; Хао, Jianxiu (2002), "Перечисление почти идеальных паросочетаний фактор-критических графов", Дискретная математика , 243 (1-3): 259-266, DOI : 10.1016 / S0012-365X (01) 00204-7 , Руководство по ремонту 1874747 .
  4. ^ Došlić, Томислав (2005), "Mycielskians и паросочетания" , Discussiones Mathematicae Теория графов , 25 (3): 261-266, DOI : 10,7151 / dmgt.1279 , МР 2232992 .
  5. ^ Favaron Одиль ; Фландрин, Эвелин; Ryjáček, Zdeněk (1997), "Фактор-критичность и расширение согласования в DCT-графах" , Discussiones Mathematicae Graph Theory , 17 (2): 271–278, CiteSeerX 10.1.1.25.6314 , doi : 10.7151 / dmgt.1054 , MR 1627955  .
  6. ↑ Gallai, T. (1963), «Neuer Beweis eines Tutte'schen Satzes», Magyar Tud. Акад. Мат. Kutató Int. Közl. , 8 : 135–139, MR 0166777 . Как цитирует Франк, Андраш ; Сегё, Ласло (2002), «Примечание о формуле сопоставления путей» (PDF) , Journal of Graph Theory , 41 (2): 110–119, CiteSeerX 10.1.1.20.7918 , doi : 10.1002 / jgt.10055 , MR 1926313   .
  7. ^ Ловас, Л. (1972), "Заметка о фактор-критических графах", Studia Sci. Математика. Hungar. , 7 : 279–280, MR 0335371 .
  8. ^ Корте, Бернхард Х .; Выген, Йенс (2008), «10.4 Ушные разложения факторно-критических графов», Комбинаторная оптимизация: теория и алгоритмы , алгоритмы и комбинаторика, 21 (4-е изд.), Springer-Verlag, стр. 235–241, ISBN 978-3-540-71843-7.
  9. ↑ Лу, Динцзюнь; Рао, Дуннинг (2004), «Характеристика критических графов факторов и алгоритм» (PDF) , Австралазийский журнал комбинаторики , 30 : 51–56, MR 2080453  .
  10. ^ Зайффарт, Карен (1993), "Упаковка и совершенный путь двойной крышки максимален плоских графов", Дискретная математика , 117 (1-3): 183-195, DOI : 10.1016 / 0012-365X (93) 90334-P , MR 1226141 .
  11. ^ Сигети, Золтан (1996), "О матроиду , определяемой ушных разбиений графов", Combinatorica , 16 (2): 233-241, DOI : 10.1007 / BF01844849 , МР 1401896 . Более ранний алгоритм сжатия минимального количества (невзвешенных) ребер для достижения факторно-критического графа см. В Frank, András (1993), «Консервативные взвешивания и разложение графов на ухо», Combinatorica , 13 (1): 65– 81, DOI : 10.1007 / BF01202790 , МР 1221177 .
  12. ^ Эдмондс, Джек (1965), "Пути, деревья и цветы", Canadian Journal математики , 17 : 449-467, DOI : 10,4153 / CJM-1965-045-4 , MR 0177907 .
  13. ^ Favaron, Одиллия (1996), "О K -фактор-критических графов" , Discussiones Mathematicae Теория графов , 16 (1): 41-51, DOI : 10,7151 / dmgt.1022 , МР 1429805 .
  14. ^ Эрдеш, П .; Füredi, Z .; Gould, RJ ; Гундерсон, DS (1995), "Экстремальные графики для пересекающихся треугольников" , Журнал комбинаторной теории , Series B, 64 (1): 89-100, DOI : 10,1006 / jctb.1995.1026 , МР 1328293 .
  15. ^ Галлаи, Т. (1963б), "Kritische графена II", публ. Математика. Inst. Hungar. Акад. Sci. , 8 : 373–395. Цитируется Stehlík, Matěj (2003), «Критические графы со связными дополнениями», Journal of Combinatorial Theory , Series B, 89 (2): 189–194, doi : 10.1016 / S0095-8956 (03) 00069-8 , MR 2017723 .
  16. ^ Сегеди, Балаж ; Szegedy, Кристиан (2006), "Симплектические пространства и ухо-разложение матроидов", Combinatorica , 26 (3): 353-377, DOI : 10.1007 / s00493-006-0020-3 , МР 2246153 .