Cograph

Материал из WEGA
Версия от 14:42, 3 марта 2011; Glk (обсуждение | вклад) (Новая страница: «''Cograph''' --- кограф. '''1.''' <math>G</math> is a '''cograph''' if <math>G</math> is the ''comparability graph'' of a ''series-parallel poset''. The clas…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Cograph' --- кограф.

1. [math]\displaystyle{ G }[/math] is a cograph if [math]\displaystyle{ G }[/math] is the comparability graph of a series-parallel poset. The class of cographs should not be confused with the class of series-parallel graphs.

The following recursive definition describes also the cographs:

(1) a one-vertex graph is a cograph;.

(2) if [math]\displaystyle{ G_{1} = (V_{1}, E_{1}) }[/math] and [math]\displaystyle{ G_{2} = (V_{2}, E_{2}) }[/math] are cographs, then [math]\displaystyle{ G = (V_{1} \cup V_{2}, E_{1} \cup E_{2}) }[/math] is also a cograph;

(3) if [math]\displaystyle{ G = (V, E) }[/math] is a cograph, then [math]\displaystyle{ \bar{G} = (V, \bar{E}) }[/math] is also a cograph;

(4) there are no other cographs.

2. A cograph is a graph without [math]\displaystyle{ P_{4} }[/math].