P4-Connected graph: различия между версиями
KEV (обсуждение | вклад) (Новая страница: «'''<math>P_4</math>-Connected graph''' --- <math>P_{4}</math>-связный граф. A graph <math>G = (V,E)</math> is '''<math>P_{4}</math>-connected graph''' i…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>P_4</math>-Connected graph''' - | '''<math>\,P_4</math>-Connected graph''' — ''[[P4-Cвязный граф|<math>\,P_{4}</math>-связный граф]].'' | ||
A graph <math>G = (V,E)</math> is '''<math>P_{4}</math>-connected graph''' if for every partition of | A [[graph, undirected graph, nonoriented graph|graph]] <math>\,G = (V,E)</math> is '''<math>\,P_{4}</math>-connected graph''' if for every partition of <math>\,V</math> into nonempty disjoint sets <math>\,V_{1}</math> and <math>\,V_{2}</math>, some chordless [[path]] on four [[vertex|vertices]] and three [[edge|edges]] (i.e. <math>\,P_{4}</math>) contains vertices from both <math>\,V_{1}</math> and <math>\,V_{2}</math>. | ||
<math>V</math> into nonempty disjoint sets <math>V_{1}</math> and <math>V_{2}</math>, some chordless | |||
path on four vertices and three edges (i.e. <math>P_{4}</math>) contains vertices | |||
from both <math>V_{1}</math> and <math>V_{2}</math>. | |||
The concept of <math>P_{4}</math>-connectedness leads to a structure theorem for | The concept of <math>\,P_{4}</math>-connectedness leads to a structure theorem for arbitrary graphs in terms of <math>\,P_{4}</math>-connected components and suggests, in a quite natural way, a [[tree]] representation unique up to ''isomorphism''. The leaves of the resulting tree are | ||
arbitrary graphs in terms of <math>P_{4}</math>-connected components and | <math>\,P_{4}</math>-connected components and weak vertices, that is, vertices belonging to no <math>\,P_{4}</math>-connected component. The structure theorem and the corresponding tree representation provide tools for the study of graphs with a simple <math>\,P_{4}</math>-structure, such as <math>\,P_{4}</math>-reducible, <math>\,P_{4}</math>-extendible, <math>\,P_{4}</math>-sparse graphs. | ||
suggests, in a quite natural way, a tree representation unique up to | |||
''isomorphism''. The leaves of the resulting tree are | ==Литература== | ||
<math>P_{4}</math>-connected components and weak vertices, that is, vertices | |||
belonging to no <math>P_{4}</math>-connected component. The structure theorem and | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
the corresponding tree | |||
graphs with a simple <math>P_{4}</math>-structure, such as <math>P_{4}</math>-reducible, | |||
<math>P_{4}</math>-extendible, <math>P_{4}</math>-sparse graphs. | |||
Текущая версия от 13:48, 18 марта 2015
[math]\displaystyle{ \,P_4 }[/math]-Connected graph — [math]\displaystyle{ \,P_{4} }[/math]-связный граф.
A graph [math]\displaystyle{ \,G = (V,E) }[/math] is [math]\displaystyle{ \,P_{4} }[/math]-connected graph if for every partition of [math]\displaystyle{ \,V }[/math] into nonempty disjoint sets [math]\displaystyle{ \,V_{1} }[/math] and [math]\displaystyle{ \,V_{2} }[/math], some chordless path on four vertices and three edges (i.e. [math]\displaystyle{ \,P_{4} }[/math]) contains vertices from both [math]\displaystyle{ \,V_{1} }[/math] and [math]\displaystyle{ \,V_{2} }[/math].
The concept of [math]\displaystyle{ \,P_{4} }[/math]-connectedness leads to a structure theorem for arbitrary graphs in terms of [math]\displaystyle{ \,P_{4} }[/math]-connected components and suggests, in a quite natural way, a tree representation unique up to isomorphism. The leaves of the resulting tree are [math]\displaystyle{ \,P_{4} }[/math]-connected components and weak vertices, that is, vertices belonging to no [math]\displaystyle{ \,P_{4} }[/math]-connected component. The structure theorem and the corresponding tree representation provide tools for the study of graphs with a simple [math]\displaystyle{ \,P_{4} }[/math]-structure, such as [math]\displaystyle{ \,P_{4} }[/math]-reducible, [math]\displaystyle{ \,P_{4} }[/math]-extendible, [math]\displaystyle{ \,P_{4} }[/math]-sparse graphs.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.