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

Материал из WikiGrapp
Перейти к:навигация, поиск
(Новая страница: «'''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.

Текущая версия на 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 \,C_{n} (i.e., a cycle of length \,n) for \,n > 3.

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.