Полунесводимый граф: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Полунесводимый граф''' (''[[Semiirreducible graph]]'') | '''Полунесводимый граф''' (''[[Semiirreducible graph]]'') — | ||
[[двудольный граф]] с <math>V = S \cup T</math> | [[двудольный граф]] с <math>V = S \cup T,</math> имеющий точно одно наименьшее | ||
[[вершинное покрытие]] <math>M</math>, причем или <math>M \cap S</math> | [[вершинное покрытие]] <math>\,M</math>, причем или <math>M \cap S,</math> или <math>M \cap T</math> пусто. | ||
Верна теорема Харари и Пламмера: | Верна теорема Харари и Пламмера: | ||
''[[Граф]] <math>G</math> и его [[реберное ядро]] <math>C_{1}(G)</math> совпадают тогда и только | ''[[Граф]] <math>\,G</math> и его [[реберное ядро]] <math>\,C_{1}(G)</math> совпадают тогда и только | ||
тогда, когда <math>G</math> является двудольным полунесводимым или [[несводимый граф|несводимым | тогда, когда <math>\,G</math> является двудольным полунесводимым или [[несводимый граф|несводимым | ||
графом]]''. | графом]]''. | ||
==Литература== | ==Литература== | ||
* Харари Ф. Теория графов. — М.: Мир, 1973. | |||
Текущая версия от 12:25, 17 июня 2011
Полунесводимый граф (Semiirreducible graph) — двудольный граф с [math]\displaystyle{ V = S \cup T, }[/math] имеющий точно одно наименьшее вершинное покрытие [math]\displaystyle{ \,M }[/math], причем или [math]\displaystyle{ M \cap S, }[/math] или [math]\displaystyle{ M \cap T }[/math] пусто.
Верна теорема Харари и Пламмера: Граф [math]\displaystyle{ \,G }[/math] и его реберное ядро [math]\displaystyle{ \,C_{1}(G) }[/math] совпадают тогда и только тогда, когда [math]\displaystyle{ \,G }[/math] является двудольным полунесводимым или несводимым графом.
Литература
- Харари Ф. Теория графов. — М.: Мир, 1973.