Полунесводимый граф: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Полунесводимый граф''' (''Semiirreducible graph'') - двудольный граф с <math>V = S \cup T</math>, и...) |
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 \cap T</math> пусто. | [[вершинное покрытие]] <math>M</math>, причем или <math>M \cap S</math>, или <math>M \cap T</math> пусто. | ||
Верна теорема Харари и Пламмера: | Верна теорема Харари и Пламмера: | ||
''Граф <math>G</math> и его реберное ядро <math>C_ | ''[[Граф]] <math>G</math> и его [[реберное ядро]] <math>C_{1}(G)</math> совпадают тогда и только | ||
тогда, когда <math>G</math> является двудольным полунесводимым или несводимым | тогда, когда <math>G</math> является двудольным полунесводимым или [[несводимый граф|несводимым | ||
графом''. | графом]]''. | ||
==Литература== | ==Литература== | ||
[Харари] | [Харари] | ||
Версия от 14:41, 23 декабря 2009
Полунесводимый граф (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] является двудольным полунесводимым или несводимым графом.
Литература
[Харари]