Cograph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «''Cograph''' --- кограф. '''1.''' <math>G</math> is a '''cograph''' if <math>G</math> is the ''comparability graph'' of a ''series-parallel poset''. The clas…»)
 
Нет описания правки
 
Строка 1: Строка 1:
''Cograph''' --- кограф.  
'''Cograph''' — ''[[кограф]]''.  


'''1.''' <math>G</math> is a '''cograph''' if <math>G</math> is the ''comparability graph'' of a ''series-parallel poset''. The class of cographs should not be confused
'''1.''' <math>\,G</math> is a '''cograph''' if <math>\,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.
with the class of series-parallel graphs.


The following recursive definition describes also the cographs:
The following recursive definition describes also the cographs:


(1) a one-vertex graph is a cograph;.
(1) a one-[[vertex]] [[graph, undirected graph, nonoriented graph|graph]] is a cograph;.


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


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


(4) there are no other cographs.
(4) there are no other cographs.


'''2.''' A '''cograph'''  is a graph without <math>P_{4}</math>.
'''2.''' A '''cograph'''  is a graph without <math>\,P_{4}</math>.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 10:46, 24 октября 2018

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].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.