1294
правки
Chordal graph: различия между версиями
Материал из WEGA
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Chordal graph''' --- хордальный граф. A graph that does not contain ''chordless cycles'' of length greater than three is called a '''chordal''' gr…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Chordal graph''' | '''Chordal graph''' — [[хордальный граф]]. | ||
A graph that does not contain ''chordless cycles'' of length greater | A [[graph, undirected graph, nonoriented graph|graph]] that does not contain ''[[chordless cycle|chordless cycles]]'' of length greater than three is called a '''chordal''' graph. This is equivalent to saying that the graph does not contain an ''[[induced (with vertices) subgraph|induced subgraph]]'' isomorphic to <math>\,C_{n}</math> (i.e., a cycle of length <math>\,n</math>) for <math>\,n > 3</math>. | ||
than three is called a '''chordal''' graph. This is equivalent to saying that the graph does not | |||
contain an '' induced subgraph'' isomorphic to <math>C_{n}</math> (i.e., a cycle | |||
of length <math>n</math>) for <math>n > 3</math>. | |||
There are many ways to characterize chordal graphs. Although many of | There are many ways to characterize chordal graphs. Although many of | ||
these characterizations are interesting and useful, it suffices to | these characterizations are interesting and useful, it suffices to | ||
list only some of them. One of the most important tools is the concept | list only some of them. One of the most important tools is the concept | ||
of a ''perfect elimination scheme''. The other way to define a chordal | of a ''[[perfect elimination scheme]]''. The other way to define a chordal | ||
graph is to consider it as an ''intersection graph'' of a family of | graph is to consider it as an ''[[intersection graph]]'' of a family of | ||
subtrees of a tree. | [[subtree|subtrees]] of a [[tree]]. | ||
An important subclass of chordal graphs is the ''interval | An important subclass of chordal graphs is the ''[[interval graph|interval graphs]]''. | ||
graphs''. | |||
Other names of a chordal graph are '''Triangulated graph, Rigid circuit graph, Perfect elimination graph, Monotone transitive graph'''. | Other names of a chordal graph are '''[[Triangulated graph]], [[Rigid circuit graph]], [[Perfect elimination graph]], [[Monotone transitive graph]]'''. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
