Cograph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «''Cograph''' --- кограф. '''1.''' <math>G</math> is a '''cograph''' if <math>G</math> is the ''comparability graph'' of a ''series-parallel poset''. The clas…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 12:33, 7 мая 2014
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.