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

Фактор-критический граф (или почти сочетаемый граф [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. Pulleyblank, Edmonds, 1974, с. 214–242.
  2. Cornuéjols, Pulleyblank, 1983, с. 35–52.
  3. 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.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.