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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 31: Строка 31:
  
 
Выберем вершину из правой компоненты.Тогда возможны варианты:
 
Выберем вершину из правой компоненты.Тогда возможны варианты:
1)Все <tex> l </tex> рёбер инцидентны вершине.Тогда:
+
 
  1.1)Если вершина не единственна - удаляем вершину.
+
1. Все <tex> l </tex> рёбер инцидентны вершине. Тогда:
  1.2)Если вершина единственная, тогда
+
 
    1.2.1)Во второй компоненте <tex> l </tex> вершин - (??)
+
# Если вершина не единственна - удаляем вершину.
    1.2.2)Удаляем её.
+
# Если вершина единственная, тогда:
2)Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинами, все левые концы, а у остальных - все правые концы.
+
##Во второй компоненте <tex> l </tex> вершин - (??).
 +
## Удаляем её.
 +
 
 +
2. Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинами, все левые концы, а у остальных - все правые концы.
  
 
}}
 
}}

Версия 04:07, 27 октября 2011

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


Определение:
Граф называется [math]k[/math] - вершинно связным, если удаление любых [math] (k - 1) [/math] вершин оставляет граф связным.


Вершинной связностью графа называется [math] \varkappa (G) = \max \{ k | G [/math] вершинно [math] k [/math] - связен [math] \} [/math].

Полный граф [math] \varkappa (K_n) = n - 1 [/math].


Определение:
Граф называется [math] l [/math] - реберно связным, если удаление любых [math] (l - 1) [/math] ребер оставляет граф связным.


Реберной связностью графа называется [math] \lambda(G) = \max \{ l | G [/math] реберно [math] l [/math] - связен [math] \} [/math]

При [math] n = 1, \lambda (K_1) = 0 [/math] .

Теорема:
[math] \varkappa (G) \leqslant \lambda (G) \leqslant \sigma (G) [/math] , где [math] \sigma(G) [/math] - минимальная степень вершин графа [math] G [/math]
Доказательство:
[math]\triangleright[/math]

[math] \lambda (G) \leqslant \sigma (G) [/math] - очевидно.

Рассмотрим граф [math] \lambda (G) = l [/math]. Покажем, что можем удалить l вершин и сделать граф несвязным.

Выберем вершину из правой компоненты.Тогда возможны варианты:

1. Все [math] l [/math] рёбер инцидентны вершине. Тогда:

  1. Если вершина не единственна - удаляем вершину.
  2. Если вершина единственная, тогда:
    1. Во второй компоненте [math] l [/math] вершин - (??).
    2. Удаляем её.
2. Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинами, все левые концы, а у остальных - все правые концы.
[math]\triangleleft[/math]


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


Определение:
Говорят, что вершины [math]u[/math] и [math]v[/math] [math]k[/math]-разделимы, если минимальная мощность множества, разделяющего [math]u[/math] и [math]v[/math] равна [math]k[/math]


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