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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 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.

Текущая версия от 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.