Изменения
Новая страница: «{{Определение |definition = '''<tex>k</tex>-фактор''' — Основные определения теории графов|регулярны…»
{{Определение
|definition = '''<tex>k</tex>-фактор''' — [[Основные определения теории графов|регулярный]] остовный подграф степени <tex>k</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>k</tex>-факторов, то их объединение называется <tex>k</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>k</tex>-факторизуемым.
}}
{{Определение
|definition = Пусть задана функция <tex>f : V(G) \rightarrow \mathbb{N}</tex>, такая что <tex>\forall~v \in V(G):f(v)\leq \text{deg}(v)</tex>. Тогда остовный подграф <tex>G_f</tex> в котором степень каждой вершины <tex>v</tex> равна <tex>f(v)</tex> называется '''<tex>f</tex>-фактором'''.
}}
== Задача о поиске произвольного <tex>f</tex>-фактора ==
Пусть дан граф <tex>G</tex> и функция <tex>f : V(G) \rightarrow \mathbb{N}</tex>. Построим граф <tex>G^*</tex> следующим образом.
# Для каждого ребра <tex>(u,w)\in E(G)</tex> добавим в граф <tex>G^*</tex> две новых вершины <tex>e(u)</tex> и <tex>e(w)</tex>, соответствующие <tex>u</tex> и <tex>w</tex>, и соединим их ребром. В результате каждой вершине <tex>v \in V(g)</tex> будет соответствовать множество <tex>S(v) \subset V(G_f^*)</tex> такое что <tex>|S(v)|=deg(v)</tex>.
# Для каждой вершины <tex>v\in V(G)</tex> добавим в <tex>G^*</tex> новые <tex>deg(v)-f(v)</tex> вершин, образующие множество <tex>T(v)</tex>. Каждую вершину из <tex>T(v)</tex> свяжем ребром с каждой вершиной из <tex>S(v)</tex>
|definition = '''<tex>k</tex>-фактор''' — [[Основные определения теории графов|регулярный]] остовный подграф степени <tex>k</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>k</tex>-факторов, то их объединение называется <tex>k</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>k</tex>-факторизуемым.
}}
{{Определение
|definition = Пусть задана функция <tex>f : V(G) \rightarrow \mathbb{N}</tex>, такая что <tex>\forall~v \in V(G):f(v)\leq \text{deg}(v)</tex>. Тогда остовный подграф <tex>G_f</tex> в котором степень каждой вершины <tex>v</tex> равна <tex>f(v)</tex> называется '''<tex>f</tex>-фактором'''.
}}
== Задача о поиске произвольного <tex>f</tex>-фактора ==
Пусть дан граф <tex>G</tex> и функция <tex>f : V(G) \rightarrow \mathbb{N}</tex>. Построим граф <tex>G^*</tex> следующим образом.
# Для каждого ребра <tex>(u,w)\in E(G)</tex> добавим в граф <tex>G^*</tex> две новых вершины <tex>e(u)</tex> и <tex>e(w)</tex>, соответствующие <tex>u</tex> и <tex>w</tex>, и соединим их ребром. В результате каждой вершине <tex>v \in V(g)</tex> будет соответствовать множество <tex>S(v) \subset V(G_f^*)</tex> такое что <tex>|S(v)|=deg(v)</tex>.
# Для каждой вершины <tex>v\in V(G)</tex> добавим в <tex>G^*</tex> новые <tex>deg(v)-f(v)</tex> вершин, образующие множество <tex>T(v)</tex>. Каждую вершину из <tex>T(v)</tex> свяжем ребром с каждой вершиной из <tex>S(v)</tex>
