Обсуждение:Факторизация графов — различия между версиями
Cczy (обсуждение | вклад) (→Задача о поиске произвольного f-фактора) |
Cczy (обсуждение | вклад) (→Задача о поиске произвольного f-фактора) |
(нет различий)
|
Текущая версия на 21:24, 29 декабря 2019
Определение: |
регулярный остовный подграф степени . Если граф представляет собой сумму -факторов, то их объединение называется -факторизацией, а сам граф назыается -факторизуемым. | -фактор —
Определение: |
Пусть задана функция | , такая что . Тогда остовный подграф в котором степень каждой вершины равна называется -фактором.
Задача о поиске произвольного -фактора
Сведем задачу о поиске
-фактора к задаче о поиске наибольшего паросочетания.Пусть дан граф
и функция . Построим граф следующим образом.- Для каждого ребра добавим в граф по одной новой вершине в множества и , и соединим их ребром . В результате каждой вершине будет соответствовать множество такое что ; Каждому ребру будет соответствовать ребро , причем ни для каких двух ребер из концы соответствующих им ребер в не пересекаются.
- Для каждой вершины добавим в новые вершин, образующие множество . Каждую вершину из свяжем ребром с каждой вершиной из . В результате для каждой вершины Множество образует полный двудольный граф.
Теорема: |
Граф имеет -фактор тогда и только тогда, когда соответствующий графу и функции граф имеет совершенное паросочетание. |
Доказательство: |
Пусть граф имеет -фактор . Построим паросочетание для графа следующим образом:
В результате каждая вершина в покрыта , следовательно является совершенным паросочетанием.Пусть имеет совершенное паросочетание . Для каждой вершины является независимым множеством и полностью покрыто , следовательно множество покрыто ребрами, концы которых лежат в , а значит каждая вершина из покрыта ребром, второй конец которого принадлежит , причем . Поэтому если мы добавим в все ребра соответствующие ребрам из покрывающим , то есть все ребра из концы которых лежат в множествах , то степень каждой вершины будет равна , а значит будет являться -фактором. |
Из доказательства напрямую следует, что для нахождения Алгоритмом Эдмондса для поиска наибольшего паросочетания.
-фактора графа достаточно найти совершенное паросочетание в графе . Т.к. в общем случае не является двудольным, для решения этой задачи можно воспользваться