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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
  
 
Вершинной связностью графа называется
 
Вершинной связностью графа называется
<tex> \varkappa (G) = \max  \{ k  |  G </tex> вершинно <tex> k </tex> - связен  <tex> \} </tex>.
+
<tex> \varkappa (G) = \max  \{ k  |  G </tex> <tex> k </tex> - вершинно связен  <tex> \} </tex>.
  
 
Полный граф <tex> \varkappa (K_n) = n - 1 </tex>.
 
Полный граф <tex> \varkappa (K_n) = n - 1 </tex>.
Строка 22: Строка 22:
 
}}
 
}}
  
Реберной связностью графа называется <tex> \lambda(G) = \max \{ l | G </tex> реберно <tex> l </tex> - связен <tex> \} </tex>
+
Реберной связностью графа называется <tex> \lambda(G) = \max \{ l | G </tex> <tex> l </tex> - реберно связен <tex> \} </tex>
  
 
При <tex> n = 1,  \lambda (K_1) = 0 </tex> .  
 
При <tex> n = 1,  \lambda (K_1) = 0 </tex> .  

Версия 06:44, 27 октября 2011

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

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


Граф [math] G [/math] является [math]k[/math] - вершинно связным [math]\Leftrightarrow [/math] любая пара его вершин соединена по крайней мере [math]k[/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] G [/math] является [math] l [/math] - реберно связным [math]\Leftrightarrow [/math] любая пара его вершин соединена по крайней мере [math] l [/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] \varkappa (G) \leqslant \lambda (G) [/math].

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

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

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

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

Если граф [math]G [/math] имеет [math]n [/math] вершин и [math] \sigma (G) \ge \left [ \frac{n}{2} \right ] \quad [/math], то [math] \lambda (G) = \sigma (G) [/math].

Смотри также

Литература

  • Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)