K-связность — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(форматирование)
(ссылки)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Граф называется <tex>k</tex>-связным, если <tex>\kappa(G) \ge k</tex>
+
Граф называется <tex>k</tex>-связным, если [[Вершинная,_реберная_связность,_связь_между_ними_и_минимальной_степенью_вершины|<tex>\kappa(G) \ge k</tex>]]
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Граф называется <tex>k</tex>-реберно связным, если <tex>\lambda(G) \ge k</tex>
+
Граф называется <tex>k</tex>-реберно связным, если [[Вершинная,_реберная_связность,_связь_между_ними_и_минимальной_степенью_вершины|<tex>\lambda(G) \ge k</tex>]]
 
}}
 
}}
  

Версия 23:26, 13 октября 2010

Связность - одна из топологических характеристик графа


Определение:
Граф называется [math]k[/math]-связным, если [math]\kappa(G) \ge k[/math]


Определение:
Граф называется [math]k[/math]-реберно связным, если [math]\lambda(G) \ge k[/math]


Определение:
Множество [math]S[/math] вершин, ребер или вершин и ребер разделяет [math]u[/math] и [math]v[/math], если [math]u[/math] и [math]v[/math] принадлежат различным компонентам графа [math]G-S[/math]


Многие утверждения для связных графов можно обобщить для случая [math]k[/math]-связности, однако аналог тривиального утверждения часто оказывается содержательным. Простейший пример - Теорема Менгера, утверждение которой для [math]k=1[/math] тривиально.