4624
правки
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. | |||