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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Граф называется '''<tex>k</tex> - вершинно связным''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным.
+
Граф называется '''<tex>k</tex> - вершинно связным''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным.
 
 
 
 
Граф <tex> G </tex>  является '''<tex>k</tex> - вершинно связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>k</tex> вершинно непересекающимися путями.
 
 
 
 
}}
 
}}
  
Строка 17: Строка 13:
 
|definition=
 
|definition=
 
Граф называется '''<tex> l </tex> - реберно связным''', если удаление любых <tex> (l - 1) </tex> ребер оставляет граф связным.  
 
Граф называется '''<tex> l </tex> - реберно связным''', если удаление любых <tex> (l - 1) </tex> ребер оставляет граф связным.  
 
 
Граф  <tex> G </tex> является '''<tex> l </tex> - реберно связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.
 
 
}}
 
}}
  
Строка 37: Строка 30:
  
 
Если граф <tex>G </tex> имеет <tex>n </tex> вершин и <tex> \sigma (G)  \ge \left [ \frac{n}{2} \right ] \quad </tex>, то  <tex>  \lambda (G) = \sigma (G) </tex>.
 
Если граф <tex>G </tex> имеет <tex>n </tex> вершин и <tex> \sigma (G)  \ge \left [ \frac{n}{2} \right ] \quad </tex>, то  <tex>  \lambda (G) = \sigma (G) </tex>.
 +
 +
 +
 +
Рассмотри граф <tex> G </tex> .
 +
 +
Пусть <tex> S </tex> - множество вершин/ребер/вершин и ребер.
 +
 +
Возьмем рассмотрим вершины <tex> u </tex> и  <tex> v </tex>.
 +
 +
<tex> S </tex> разделяет <tex> u </tex> и <tex> v </tex>, если <tex> u, v </tex> принадлежат разным компонентам связности графа <tex> G \smallsetminus S </tex>.
 +
 +
 +
Отсюда справедливы следующие утверждения:
 +
 +
Наименьшее число вершин, разделяющих две несмежные вершины <tex> u </tex> и <tex> v </tex>, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих <tex> u </tex> и <tex> v </tex>.
 +
 +
 +
* Граф <tex> G </tex>  является '''<tex>k</tex> - вершинно связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>k</tex> вершинно непересекающимися путями.
 +
 +
 +
* Граф  <tex> G </tex> является '''<tex> l </tex> - реберно связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.
 +
  
 
==Смотри также==
 
==Смотри также==
Строка 45: Строка 60:
 
* Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
 
* Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
  
 
+
* Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966
 
[[Категория:Связность в графах]]
 
[[Категория:Связность в графах]]

Версия 05:09, 3 ноября 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]\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].


Рассмотри граф [math] G [/math] .

Пусть [math] S [/math] - множество вершин/ребер/вершин и ребер.

Возьмем рассмотрим вершины [math] u [/math] и [math] v [/math].

[math] S [/math] разделяет [math] u [/math] и [math] v [/math], если [math] u, v [/math] принадлежат разным компонентам связности графа [math] G \smallsetminus S [/math].


Отсюда справедливы следующие утверждения:

Наименьшее число вершин, разделяющих две несмежные вершины [math] u [/math] и [math] v [/math], равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих [math] u [/math] и [math] v [/math].


  • Граф [math] G [/math] является [math]k[/math] - вершинно связным [math]\Leftrightarrow [/math] любая пара его вершин соединена по крайней мере [math]k[/math] вершинно непересекающимися путями.


  • Граф  [math] G [/math] является [math] l [/math] - реберно связным [math]\Leftrightarrow [/math] любая пара его вершин соединена по крайней мере [math] l [/math] - реберно непересекающимися путями.


Смотри также

Литература

  • Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
  • Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966