Фактор-критический граф

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

Фактор-критический граф (или почти сочетаемый граф [1][2].) — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание. (Совершенное паросочетание в графе — это подмножество рёбер со свойством, что каждая из вершин графа является конечной вершиной в точности одного ребра из подмножества.)

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

Примеры

Три графа дружеских отношений, примеры негамильтоновых фактор-критических графов
Cкрученно удлинённая пятиугольная пирамида[англ.], фактор-критический граф без клешней

Любой цикл нечётной длины является фактор-критическим[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].

Приложения

Цветок — это фактор-критический подграф большего графа. Цветки играют ключевую роль в алгоритмах Эдмондса[англ.] поиска наибольшего паросочетания и минимального взвешенного совершенного сочетания в недвудольных графах[13].

В комбинаторике многогранников фактор-критические графы играют важную роль при описании фасет многогранников паросочетаний заданного графа[1][2].

Обобщения и связанные концепции

Говорят, что граф k-фактор критический, если любое подмножество из n − k вершин имеет совершенное паросочетание. При таком определении почти сочетаемый (en:hypomatchable) граф является 1-фактор-критическим[14]. Даже более обще, граф является (a,b)-фактор-критическим, если любое подмножество из n − k вершин имеет r-фактор, то есть он является набором вершин r-регулярного подграфа заданного графа.

Когда говорят о критическом графе (без уточнения k-), обычно имеют в виду граф, удаление любой вершины которого приводит к уменьшению числа цветов, необходимых для раскраски графа. Понятие критичности используется значительно шире в теории графов для графов, в которых удаление любой вершины изменяет какое-то свойство графа. Критичный по сочетаниям граф — это граф, для которого удаление любой вершины не изменяет размера наибольшего паросочетания. Согласно Галлаи, критичные по сочетаниям графы, это в точности графы, в которых любая связная компонента является фактор-критической[15]. Дополнение критического графа обязательно критично по сочетаниям, факт, который использовал Галлаи для доказательства нижней границы числа вершин критического графа[16].

Вне теории графов понятие фактор-критичности имеет расширение на матроиды путём определения типа ушного разложения на матроидах. Матроид является фактор-критическим, если он имеет ушное разложение, в котором все уши нечётные[17].

Примечания

  1. ↑ 1 2 3 4 Pulleyblank, Edmonds, 1974, с. 214–242.
  2. ↑ 1 2 Cornuéjols, Pulleyblank, 1983, с. 35–52.
  3. ↑ 1 2 Liu, Hao, 2002, с. 259–266.
  4. ↑ Došlić, 2005, с. 261–266.
  5. ↑ Favaron, Flandrin, Ryjáček, 1997, с. 271–278.
  6. ↑ Gallai, 1963, с. 135–139.
  7. ↑ Lovász, 1972, с. 279–280.
  8. ↑ Korte, Vygen, 2008, с. 235–241.
  9. ↑ Lou, Rao, 2004, с. 51–56.
  10. ↑ Seyffarth, 1993, с. 183–195.
  11. ↑ Szigeti, 1996, с. 233–241.
  12. ↑ Frank, 1993, с. 65–81.
  13. ↑ Edmonds, 1965, с. 449–467.
  14. ↑ Favaron, 1996, с. 41–51.
  15. ↑ Erdős, Füredi, Gould, Gunderson, 1995, с. 89–100.
  16. ↑ Gallai, 1963b, с. 373–395.
  17. ↑ Szegedy, Szegedy, 2006, с. 353–377.

Литература

  • L. Lovász. A note on factor-critical graphs // Studia Sci. Math. Hungar.. — 1972. — Т. 7. — С. 279–280.
  • Bernhard H. Korte, Jens Vygen. 10.4 Ear-Decompositions of Factor-Critical Graphs // Combinatorial Optimization: Theory and Algorithms. — 4th. — Springer-Verlag, 2008. — Т. 21. — С. 235–241. — (Algorithms and Combinatorics). — ISBN 978-3-540-71843-7.
  • W. R. Pulleyblank, J. Edmonds. Facets of 1-matching polyhedra // Hypergraph Seminar / C. Berge, D. K. Ray-Chaudhuri. — Springer-Verlag, 1974. — Т. 411. — С. 214–242. — (Lecture Notes in Mathematics). — ISBN 978-3-540-06846-4. — doi:10.1007/BFb0066196.
  • Jack Edmonds. Paths, Trees and Flowers // Canadian Journal of Mathematics. — 1965. — Т. 17. — doi:10.4153/CJM-1965-045-4.
  • Dingjun Lou, Dongning Rao. Characterizing factor critical graphs and an algorithm // The Australasian Journal of Combinatorics. — 2004. — Т. 30. — С. 51–56.
  • Karen Seyffarth. Packings and perfect path double covers of maximal planar graphs // Discrete Mathematics. — 1993. — Т. 117, вып. 1–3. — С. 183–195. — doi:10.1016/0012-365X(93)90334-P.
  • G. Cornuéjols, W. R. Pulleyblank. Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem // Combinatorica. — 1983. — Т. 3, вып. 1. — doi:10.1007/BF02579340.
  • Tomislav Došlić. Mycielskians and matchings // Discussiones Mathematicae Graph Theory. — 2005. — Т. 25, вып. 3. — С. 261–266.
  • Odile Favaron, Evelyne Flandrin, Zdeněk Ryjáček. Factor-criticality and matching extension in DCT-graphs // Discussiones Mathematicae Graph Theory. — 1997. — Т. 17, вып. 2. — С. 271–278.
  • Tibor Gallai. Neuer Beweis eines Tutte'schen Satzes // Magyar Tud. Akad. Mat. Kutató Int. Közl.. — 1963. — Т. 8. — С. 135–139.. Как процитировано у Франко и Сегё (Frank, Szegő 2002)
  • András Frank, László Szegő. Note on the path-matching formula // Journal of Graph Theory. — 2002. — Т. 41, вып. 2. — С. 110–119. — doi:10.1002/jgt.10055.
  • Yan Liu, Jianxiu Hao. The enumeration of near-perfect matchings of factor-critical graphs // Discrete Mathematics. — 2002. — Т. 243, вып. 1–3. — С. 259–266. — doi:10.1016/S0012-365X(01)00204-7.
  • Zoltán Szigeti. On a matroid defined by ear-decompositions of graphs // Combinatorica. — 1996. — Т. 16, вып. 2. — С. 233–241. — doi:10.1007/BF01844849.
  • András Frank. Conservative weightings and ear-decompositions of graphs // Combinatorica. — 1993. — Т. 13, вып. 1. — С. 65–81. — doi:10.1007/BF01202790.
  • Odile Favaron. On k-factor-critical graphs // Discussiones Mathematicae Graph Theory. — 1996. — Т. 16, вып. 1. — С. 41–51.
  • P. Erdős, Z. Füredi, R. J. Gould, D. S. Gunderson. Extremal graphs for intersecting triangles // Journal of Combinatorial Theory. — 1995. — Т. 64, вып. 1. — С. 89–100. — doi:10.1006/jctb.1995.1026.
  • T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963b. — Т. 8. — С. 373–395.. Как процитировано у Штехлика ((sfn|Stehlík|2003}}
  • Matěj Stehlík. Critical graphs with connected complements // Journal of Combinatorial Theory. — 2003. — Т. 89, вып. 2. — С. 189–194. — doi:10.1016/S0095-8956(03)00069-8.
  • Balázs Szegedy, Christian Szegedy. Symplectic spaces and ear-decomposition of matroids // Combinatorica. — 2006. — Т. 26, вып. 3. — С. 353–377. — doi:10.1007/s00493-006-0020-3.