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

Материал из WikiGrapp
Перейти к:навигация, поиск
(Создана новая страница размером '''Несводимый граф''' (''Irreducible graph'') - двудольный граф с множеством вершин <math>V ...)
 
 
(не показана 1 промежуточная версия этого же участника)
Строка 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>, причем
 
или <math>M_{1} \cap S</math> и <math>M_{2} \cap T</math> пусты, или <math>M_{1} \cap T</math> и <math>M_{2}
 
или <math>M_{1} \cap S</math> и <math>M_{2} \cap T</math> пусты, или <math>M_{1} \cap T</math> и <math>M_{2}
 
\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.