4624
правки
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. | |||