Вершинная, рёберная связность, связь между ними и минимальной степенью вершины — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''''Вершинной связностью''''' <math>\varkappa</math> графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
+
'''''Вершинной связностью''''' <tex>\varkappa</tex> графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''''Реберной связностью''''' <math>\mathcal\lambda</math> графа G называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
+
'''''Реберной связностью''''' <tex>\lambda</tex> графа G называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
 
}}
 
}}
  
Строка 12: Строка 12:
 
|statement=
 
|statement=
 
Для любого графа G справедливо следующее неравенство:<br/>
 
Для любого графа G справедливо следующее неравенство:<br/>
−
<math>\varkappa \le\mathcal\lambda \le \mathcal \delta </math><ref><math>\mathcal\delta</math> - минимальная степень вершины графа G</ref>
+
<tex>\varkappa \le\lambda \le \delta </tex><ref><tex>\delta</tex> - минимальная степень вершины графа G</ref>
 
|proof=
 
|proof=
−
1) Проверим второе неравенство. Если в графе G нет ребер, то <math> \mathcal\lambda = 0 </math>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <math> \lambda \le \delta </math>. <br/>
+
1) Проверим второе неравенство. Если в графе G нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \le \delta </tex>. <br/>
−
2) Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. Если  '''G'''  - несвязный или тривиальный граф, то  <math> \varkappa = \lambda = 0 </math>. Если G связен и имеет мост x, то <math>\mathcal\lambda = 1 </math>. В последнем случае <math> \varkappa = 1 </math>, поскольку или граф G имеет точку сочленения, инцидентную ребру x, или же G = K<sub>2</sub>. Наконец, предположим, что граф G содержит множество из <math> \lambda \ge 2 </math> ребер, удаление которых делает его несвязным. Ясно, что удаляя <math>\mathcal\lambda - 1 </math> ребер из этого множества получаем граф, имеющий мост x = uv. Для каждого из этих <math>\mathcal\lambda - 1 </math> ребер выберем какую-либо инцидентную с ним вершину отличную от u и v.  Удаление выбранных вершин приводит к удалению <math>\mathcal\lambda - 1 </math> (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то <math>\varkappa < \lambda </math>; если же он связен, то в нем есть мост x, и поэтому удаление вершины u или ''v'' приводит либок несвязному, либо к тривиальному графу. в любом случае <math> \varkappa \le \lambda</math>.
+
2) Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. Если  '''G'''  - несвязный или тривиальный граф, то  <tex> \varkappa = \lambda = 0 </tex>. Если G связен и имеет мост x, то <tex>\lambda = 1 </tex>. В последнем случае <tex> \varkappa = 1 </tex>, поскольку или граф G имеет точку сочленения, инцидентную ребру x, или же G = K<sub>2</sub>. Наконец, предположим, что граф G содержит множество из <tex> \lambda \ge 2 </tex> ребер, удаление которых делает его несвязным. Ясно, что удаляя <tex>\lambda - 1 </tex> ребер из этого множества получаем граф, имеющий мост x = uv. Для каждого из этих <tex>\lambda - 1 </tex> ребер выберем какую-либо инцидентную с ним вершину отличную от u и v.  Удаление выбранных вершин приводит к удалению <tex>\lambda - 1 </tex> (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то <tex>\varkappa < \lambda </tex>; если же он связен, то в нем есть мост x, и поэтому удаление вершины u или ''v'' приводит либок несвязному, либо к тривиальному графу. в любом случае <tex> \varkappa \le \lambda</tex>.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
  Для любых натуральных чисел a, b, c, таких что a &le; b &le; c, существует граф G, у которого <math>\varkappa  = a, \lambda  = b</math> и <math>\mathcal\delta = c </math>.
+
  Для любых натуральных чисел a, b, c, таких что a &le; b &le; c, существует граф G, у которого <tex>\varkappa  = a, \lambda  = b</tex> и <tex>\delta = c </tex>.
 
|proof=
 
|proof=
−
  Рассмотрим граф G, являющийся объединением двух полных графов <math>G_1</math> и <math>G_2</math>, содержащих c + 1 вершину. Отметим b вершин, принадлежащих подграфу <math>G_1</math> и a вершин, принадлежащих подграфу <math>G_2</math>. Добавим в граф G b ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в  подграфе <math>G_1</math> и помеченной вершине, лежащей в подграфе <math>G_2</math>, причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей.
+
  Рассмотрим граф G, являющийся объединением двух полных графов <tex>G_1</tex> и <tex>G_2</tex>, содержащих c + 1 вершину. Отметим b вершин, принадлежащих подграфу <tex>G_1</tex> и a вершин, принадлежащих подграфу <tex>G_2</tex>. Добавим в граф G b ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в  подграфе <tex>G_1</tex> и помеченной вершине, лежащей в подграфе <tex>G_2</tex>, причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей.
 
Тогда: <br>
 
Тогда: <br>
−
1) Поскольку b &le; c, то было как минимум две непомеченные вершины, поэтому <math> \mathcal \delta</math> = с, так как минимальные степени вершин графов <math>G_1</math> и <math>G_2</math> была c, а степени их вершин не уменьшались.<br>
+
1) Поскольку b &le; c, то было как минимум две непомеченные вершины, поэтому <tex> \delta</tex> = с, так как минимальные степени вершин графов <tex>G_1</tex> и <tex>G_2</tex> была c, а степени их вершин не уменьшались.<br>
−
2) Заметим, что между двумя вершинами графа G существует не меньше a вершинно-непересекающихся простых цепей, следовательно по [[теорема Менгера|теореме Менгера]] <math>\varkappa </math> &ge; a. Однако если удалить из графа G помеченные вершины его подграфа <math>G_2</math>, то граф G потеряет связность. Значит, <math>\varkappa </math> = a.<br>
+
2) Заметим, что между двумя вершинами графа G существует не меньше a вершинно-непересекающихся простых цепей, следовательно по [[теорема Менгера|теореме Менгера]] <tex>\varkappa </tex> &ge; a. Однако если удалить из графа G помеченные вершины его подграфа <tex>G_2</tex>, то граф G потеряет связность. Значит, <tex>\varkappa </tex> = a.<br>
−
3) Аналогично рассуждению пункта 2, легко убедится, что <math>\mathcal\lambda </math> = b.
+
3) Аналогично рассуждению пункта 2, легко убедится, что <tex>\lambda </tex> = b.
 
}}
 
}}
 
<references/>
 
<references/>

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

Определение:
Вершинной связностью [math]\varkappa[/math] графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.


Определение:
Реберной связностью [math]\lambda[/math] графа G называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.


Теорема:
Для любого графа G справедливо следующее неравенство:
[math]\varkappa \le\lambda \le \delta [/math][1]
Доказательство:
[math]\triangleright[/math]

1) Проверим второе неравенство. Если в графе G нет ребер, то [math] \lambda = 0 [/math]. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае [math] \lambda \le \delta [/math].

2) Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. Если G - несвязный или тривиальный граф, то [math] \varkappa = \lambda = 0 [/math]. Если G связен и имеет мост x, то [math]\lambda = 1 [/math]. В последнем случае [math] \varkappa = 1 [/math], поскольку или граф G имеет точку сочленения, инцидентную ребру x, или же G = K2. Наконец, предположим, что граф G содержит множество из [math] \lambda \ge 2 [/math] ребер, удаление которых делает его несвязным. Ясно, что удаляя [math]\lambda - 1 [/math] ребер из этого множества получаем граф, имеющий мост x = uv. Для каждого из этих [math]\lambda - 1 [/math] ребер выберем какую-либо инцидентную с ним вершину отличную от u и v. Удаление выбранных вершин приводит к удалению [math]\lambda - 1 [/math] (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то [math]\varkappa \lt \lambda [/math]; если же он связен, то в нем есть мост x, и поэтому удаление вершины u или v приводит либок несвязному, либо к тривиальному графу. в любом случае [math] \varkappa \le \lambda[/math].
[math]\triangleleft[/math]
Теорема:
Для любых натуральных чисел a, b, c, таких что a ≤ b ≤ c, существует граф G, у которого [math]\varkappa = a, \lambda = b[/math] и [math]\delta = c [/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим граф G, являющийся объединением двух полных графов [math]G_1[/math] и [math]G_2[/math], содержащих c + 1 вершину. Отметим b вершин, принадлежащих подграфу [math]G_1[/math] и a вершин, принадлежащих подграфу [math]G_2[/math]. Добавим в граф G b ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе [math]G_1[/math] и помеченной вершине, лежащей в подграфе [math]G_2[/math], причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей. Тогда:
1) Поскольку b ≤ c, то было как минимум две непомеченные вершины, поэтому [math] \delta[/math] = с, так как минимальные степени вершин графов [math]G_1[/math] и [math]G_2[/math] была c, а степени их вершин не уменьшались.
2) Заметим, что между двумя вершинами графа G существует не меньше a вершинно-непересекающихся простых цепей, следовательно по теореме Менгера [math]\varkappa [/math] ≥ a. Однако если удалить из графа G помеченные вершины его подграфа [math]G_2[/math], то граф G потеряет связность. Значит, [math]\varkappa [/math] = a.

3) Аналогично рассуждению пункта 2, легко убедится, что [math]\lambda [/math] = b.
[math]\triangleleft[/math]
  1. ↑ [math]\delta[/math] - минимальная степень вершины графа G
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Вершинная,_рёберная_связность,_связь_между_ними_и_минимальной_степенью_вершины&oldid=3833»