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

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''<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…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''<math>P_4</math>-Connected graph''' --- <math>P_{4}</math>-связный граф.  
'''<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 repre\-sen\-ta\-tion 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.

Навигация