Chordal graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Chordal graph''' --- хордальный граф. A graph that does not contain ''chordless cycles'' of length greater than three is called a '''chordal''' gr…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 18:12, 28 марта 2013
Chordal graph — хордальный граф.
A graph that does not contain 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 subgraph isomorphic to [math]\displaystyle{ \,C_{n} }[/math] (i.e., a cycle of length [math]\displaystyle{ \,n }[/math]) for [math]\displaystyle{ \,n \gt 3 }[/math].
There are many ways to characterize chordal graphs. Although many of these characterizations are interesting and useful, it suffices to 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 graph is to consider it as an intersection graph of a family of subtrees of a tree.
An important subclass of chordal graphs is the interval graphs.
Other names of a chordal graph are Triangulated graph, Rigid circuit graph, Perfect elimination graph, Monotone transitive graph.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.