Викиконспекты - Вклад участника [ru]

Рёберное ядро

2016-01-11T13:31:12Z

188.162.65.2:

{{Определение|
definition=
'''Рёберное ядро''' <tex>C_1(G)</tex> графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.
}}
{{Определение|
definition=
'''Вершинным покрытием''' графа <tex>G</tex> называется такое множество <tex>V</tex> его вершин, что у любого ребра в <tex>G</tex> хотя бы одна из вершин лежит в <tex>V</tex>.
}}
{{Определение|
definition=
'''числом вершинного покрытия''' называется число вершин в наименьшем вершинном покрытии графа <tex>G</tex>.
}}
==Критерий существования реберного ядра==
{{Определение|
definition=
Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним''', если для любого подмножества <tex>M' \subseteq M</tex> выполняется неравнство <tex>|M'| \leqslant |U(M')|</tex>, где <tex>U(M') = \{v| \:v \in V(G) \setminus M, \: vu \in E(G), \: u \in M'\}</tex>
}}
{{Теорема|
statement=
для произвольного графа <tex>G</tex> следующие утверждения эквивалентны:
(1) <tex>G</tex> имеет рёберное ядро. <br>
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
}}
==Ребероне ядро в двудольном графе==
Здесь и далее будем рассматривать двудольный граф <tex>G</tex>, в котором обозначим <tex>S</tex> - множество вершин левой доли, <tex>T</tex> - множество вершин правой доли.
{{Определение |
definition= <tex>G</tex> {{---}} '''полунесводимый граф''', если <tex>G</tex> имеет ровно одно вершинное покрытие <tex>M</tex>, такое что или <tex>M \cap S</tex> или <tex>M \cap T</tex> {{---}} пусто
}}
{{Определение|
definition=
<tex>G</tex> {{---}} '''несводимый''' граф, если он имеет ровно два наименьших вершинных покрытия <tex>M_1</tex> и <tex>M_2</tex>, таких что либо <tex>M_1 \cap S \cup M_2 \cap T = \varnothing </tex>, либо <tex>M_2 \cap S \cup M_1 \cap T = \varnothing</tex>
}}
{{Определение|
definition=
<tex>G</tex> {{---}} '''сводимый граф''' если он не является ни полунесводимым, ни сводимым.
}}
{{Теорема|
statement=
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
}}

Рёберное ядро

2016-01-11T13:30:23Z

188.162.65.2:

{{Определение|
definition=
'''Рёберное ядро''' графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.
}}
{{Определение|
definition=
'''Вершинным покрытием''' графа <tex>G</tex> называется такое множество <tex>V</tex> его вершин, что у любого ребра в <tex>G</tex> хотя бы одна из вершин лежит в <tex>V</tex>.
}}
{{Определение|
definition=
'''числом вершинного покрытия''' называется число вершин в наименьшем вершинном покрытии графа <tex>G</tex>.
}}
==Критерий существования реберного ядра==
{{Определение|
definition=
Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним''', если для любого подмножества <tex>M' \subseteq M</tex> выполняется неравнство <tex>|M'| \leqslant |U(M')|</tex>, где <tex>U(M') = \{v| \:v \in V(G) \setminus M, \: vu \in E(G), \: u \in M'\}</tex>
}}
{{Теорема|
statement=
для произвольного графа <tex>G</tex> следующие утверждения эквивалентны:
(1) <tex>G</tex> имеет рёберное ядро. <br>
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
}}
==Ребероне ядро в двудольном графе==
Здесь и далее будем рассматривать двудольный граф <tex>G</tex>, в котором обозначим <tex>S</tex> - множество вершин левой доли, <tex>T</tex> - множество вершин правой доли.
{{Определение |
definition= <tex>G</tex> {{---}} '''полунесводимый граф''', если <tex>G</tex> имеет ровно одно вершинное покрытие <tex>M</tex>, такое что или <tex>M \cap S</tex> или <tex>M \cap T</tex> {{---}} пусто
}}
{{Определение|
definition=
<tex>G</tex> {{---}} '''несводимый''' граф, если он имеет ровно два наименьших вершинных покрытия <tex>M_1</tex> и <tex>M_2</tex>, таких что либо <tex>M_1 \cap S \cup M_2 \cap T = \varnothing </tex>, либо <tex>M_2 \cap S \cup M_1 \cap T = \varnothing</tex>
}}
{{Определение|
definition=
<tex>G</tex> {{---}} '''сводимый граф''' если он не является ни полунесводимым, ни сводимым.
}}
{{Теорема|
statement=
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
}}

Рёберное ядро

2016-01-11T13:28:27Z

188.162.65.2:

{{Определение|
definition=
'''Рёберное ядро''' графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.
}}
{{Определение|
definition=
'''числом вершинного покрытия''' называется число вершин в наименьшем вершинном покрытии графа <tex>G</tex>.
}}
==Критерий существования реберного ядра==
{{Определение|
definition=
Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним''', если для любого подмножества <tex>M' \subseteq M</tex> выполняется неравнство <tex>|M'| \leqslant |U(M')|</tex>, где <tex>U(M') = \{v| \:v \in V(G) \setminus M, \: vu \in E(G), \: u \in M'\}</tex>
}}
{{Теорема|
statement=
для произвольного графа <tex>G</tex> следующие утверждения эквивалентны:
(1) <tex>G</tex> имеет рёберное ядро. <br>
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
}}
==Ребероне ядро в двудольном графе==
Здесь и далее будем рассматривать двудольный граф <tex>G</tex>, в котором обозначим <tex>S</tex> - множество вершин левой доли, <tex>T</tex> - множество вершин правой доли.
{{Определение |
definition= <tex>G</tex> {{---}} '''полунесводимый граф''', если <tex>G</tex> имеет ровно одно вершинное покрытие <tex>M</tex>, такое что или <tex>M \cap S</tex> или <tex>M \cap T</tex> {{---}} пусто
}}
{{Определение|
definition=
<tex>G</tex> {{---}} '''несводимый''' граф, если он имеет ровно два наименьших вершинных покрытия <tex>M_1</tex> и <tex>M_2</tex>, таких что либо <tex>M_1 \cap S \cup M_2 \cap T = \varnothing </tex>, либо <tex>M_2 \cap S \cup M_1 \cap T = \varnothing</tex>
}}
{{Определение|
definition=
<tex>G</tex> {{---}} '''сводимый граф''' если он не является ни полунесводимым, ни сводимым.
}}
{{Теорема|
statement=
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
}}