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

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

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

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

Примеры[править | править код]

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

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

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

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

Описание[править | править код]

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

  • Тибор Галлаи[en] доказал, что граф является фактор-критическим тогда и только тогда, когда он связен и для любой вершины 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 вершин) имеет по меньшей мере mc + 1 различных почти совершенных паросочетаний. Графы, для которых эти границы точны, можно описать как имеющие ушное разложение специфичного вида[3].

Любой связный граф можно преобразовать в фактор-критический граф путём стягивания достаточно много рёбер. Минимальный набор рёбер, которые нужно стянуть, чтобы сделать заданный граф G фактор-критическим, образует базис матроида, факт, из которого следует, что работающий за полиномиальное время жадный алгоритм может быть использован для поиска наименьшего взвешенного множества рёбер, стягивание которых делает граф фактор-критическим[11]. Ранний алгоритм стягивания минимального числа (невзвешенных) рёбер для получения фактор-критического графа можно найти в статье Франка[12].

Приложения[править | править код]

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

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

Обобщения и связанные концепции[править | править код]

Говорят, что граф k-фактор критический, если любое подмножество из nk вершин имеет совершенное паросочетание. При таком определении почти сочетаемый (en:hypomatchable) граф является 1-фактор-критическим[14]. Даже более обще, граф является (a,b)-фактор-критическим, если любое подмножество из nk вершин имеет 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.

Литература[править | править код]