K-Connected graph

Материал из WikiGrapp

[math]\displaystyle{ \,k }[/math]-Connected graph[math]\displaystyle{ \,k }[/math]-связный граф.

A graph [math]\displaystyle{ \,G }[/math] is [math]\displaystyle{ \,k }[/math]-connected if there exist [math]\displaystyle{ \,k }[/math] internally node-disjoint chains between every pair of distinct nodes in [math]\displaystyle{ \,G }[/math]. A [math]\displaystyle{ \,k }[/math]-connected graph [math]\displaystyle{ \,G }[/math] is minimal if for any edge [math]\displaystyle{ \,e \in E }[/math], [math]\displaystyle{ \,G - e }[/math] is not [math]\displaystyle{ \,k }[/math]-connected. Usually, [math]\displaystyle{ \,2 }[/math]-connected graphs are called biconnected graphs and [math]\displaystyle{ \,3 }[/math]-connected graphs are called triconnected graphs.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.