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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Chordal graph''' --- хордальный граф. A graph that does not contain ''chordless cycles'' of length greater than three is called a '''chordal''' gr…»)
 
Нет описания правки
 
Строка 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.

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

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.