Несводимый граф — различия между версиями

Материал из WikiGrapp
Перейти к:навигация, поиск
 
Строка 1: Строка 1:
'''Несводимый граф''' (''[[Irreducible graph]]'') -
+
'''Несводимый граф''' (''[[Irreducible graph]]'')
 
[[двудольный граф]] с множеством [[вершина|вершин]] <math>V = S \cup T</math>, имеющий в
 
[[двудольный граф]] с множеством [[вершина|вершин]] <math>V = S \cup T</math>, имеющий в
 
точности два наименьших [[вершинное покрытие|вершинных покрытия]] <math>M_{1}, \; M_{2}</math>, причем
 
точности два наименьших [[вершинное покрытие|вершинных покрытия]] <math>M_{1}, \; M_{2}</math>, причем
Строка 5: Строка 5:
 
\cap S</math> пусты.
 
\cap S</math> пусты.
 
==Литература==
 
==Литература==
[Харари]
+
* Харари Ф. Теория графов. —  М.: Мир, 1973.

Текущая версия на 12:05, 19 мая 2011

Несводимый граф (Irreducible graph) — двудольный граф с множеством вершин V = S \cup T, имеющий в точности два наименьших вершинных покрытия M_{1}, \; M_{2}, причем или M_{1} \cap S и M_{2} \cap T пусты, или M_{1} \cap T и M_{2}
\cap S пусты.

Литература

  • Харари Ф. Теория графов. — М.: Мир, 1973.