Обсуждение:Факторизация графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = '''<tex>k</tex>-фактор''' — Основные определения теории графов|регулярны…»)
(нет различий)

Версия 03:56, 28 декабря 2019

Определение:
[math]k[/math]-факторрегулярный остовный подграф степени [math]k[/math]. Если граф [math]G[/math] представляет собой сумму [math]k[/math]-факторов, то их объединение называется [math]k[/math]-факторизацией, а сам граф [math]G[/math] назыается [math]k[/math]-факторизуемым.


Определение:
Пусть задана функция [math]f : V(G) \rightarrow \mathbb{N}[/math], такая что [math]\forall~v \in V(G):f(v)\leq \text{deg}(v)[/math]. Тогда остовный подграф [math]G_f[/math] в котором степень каждой вершины [math]v[/math] равна [math]f(v)[/math] называется [math]f[/math]-фактором.


Задача о поиске произвольного [math]f[/math]-фактора

Пусть дан граф [math]G[/math] и функция [math]f : V(G) \rightarrow \mathbb{N}[/math]. Построим граф [math]G^*[/math] следующим образом.

  1. Для каждого ребра [math](u,w)\in E(G)[/math] добавим в граф [math]G^*[/math] две новых вершины [math]e(u)[/math] и [math]e(w)[/math], соответствующие [math]u[/math] и [math]w[/math], и соединим их ребром. В результате каждой вершине [math]v \in V(g)[/math] будет соответствовать множество [math]S(v) \subset V(G_f^*)[/math] такое что [math]|S(v)|=deg(v)[/math].
  2. Для каждой вершины [math]v\in V(G)[/math] добавим в [math]G^*[/math] новые [math]deg(v)-f(v)[/math] вершин, образующие множество [math]T(v)[/math]. Каждую вершину из [math]T(v)[/math] свяжем ребром с каждой вершиной из [math]S(v)[/math]