Полунесводимый граф: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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_{1}(G)</math> совпадают тогда и только
''[[Граф]]  <math>\,G</math> и его [[реберное ядро]] <math>\,C_{1}(G)</math> совпадают тогда и только
тогда, когда <math>G</math> является  двудольным  полунесводимым  или  [[несводимый граф|несводимым
тогда, когда <math>\,G</math> является  двудольным  полунесводимым  или  [[несводимый граф|несводимым
графом]]''.
графом]]''.
==Литература==
==Литература==
[Харари]
* Харари Ф. Теория графов. —  М.: Мир, 1973.

Навигация