K-Connected graph

Материал из WEGA
Перейти к навигации Перейти к поиску

[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, 2-connected graphs are called biconnected graphs and 3-connected graphs are called triconnected graphs.