K-связность - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:10Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:29, 1 сентября 2022

2022-09-01T06:29:09Z

Vsklamm в 00:05, 21 октября 2018

2018-10-21T00:05:46Z

Shersh: /* Смотри также */

2015-12-30T01:46:27Z

‎Смотри также

91.151.202.175 в 01:25, 30 декабря 2015

2015-12-30T01:25:40Z

91.151.202.175 в 01:22, 30 декабря 2015

2015-12-30T01:22:52Z

91.151.202.175 в 01:13, 30 декабря 2015

2015-12-30T01:13:46Z

Proshev в 00:16, 18 января 2012

2012-01-18T00:16:28Z

Kirelagin: Дарю

2011-12-25T01:24:09Z

Дарю

Igor buzhinsky в 03:32, 7 ноября 2011

2011-11-07T03:32:22Z

@@ Строка 1: / Строка 1: @@
 <tex>k</tex>-cвязность {{---}} одна из топологических характеристик графа.
 {{Определение
@@ Строка 60: / Строка 39: @@
 {{Утверждение
 |statement=
-Граф  <tex> G </tex> является '''реберно  <tex>l</tex>-связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>l</tex>-реберно непересекающимися путями.
+Граф  <tex> G </tex> является '''реберно  <tex>l</tex>-связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>l</tex>-реберно непересекающимися путями.
 }}

@@ Строка 1: / Строка 1: @@
 <tex>k</tex>-cвязность {{---}} одна из топологических характеристик графа.
 {{Определение
@@ Строка 39: / Строка 60: @@
 {{Утверждение
 |statement=
-Граф  <tex> G </tex> является '''реберно  <tex>l</tex>-связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>l</tex>-реберно непересекающимися путями.
+Граф  <tex> G </tex> является '''реберно  <tex>l</tex>-связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>l</tex>-реберно непересекающимися путями.
 }}

@@ Строка 1: / Строка 1: @@
 <tex>k</tex>-cвязность {{---}} одна из топологических характеристик графа.
 {{Определение
 |definition=
 Граф называется '''вершинно  <tex>k</tex>-связным''', если удаление любых  <tex> (k  -  1) </tex>  вершин оставляет граф связным.
@@ Строка 9: / Строка 10: @@
 {{Определение
 |definition=
 Граф называется '''реберно <tex>l</tex>-связным''', если удаление любых <tex> (l - 1) </tex> ребер оставляет граф связным.

@@ Строка 40: / Строка 40: @@
 }}
-==Смотри также==
+==См. также==
 * [[Теорема Менгера]]
 * [[Теорема Менгера, альтернативное доказательство]]

@@ Строка 22: / Строка 22: @@
 Пусть <tex> S </tex> {{---}} множество вершин/ребер/вершин и ребер.
-<tex> S </tex> разделяет <tex> u </tex> и <tex> v </tex>, если <tex> u </tex> и <tex> v </tex> принадлежат разным компонентам связности графа <tex> G \smallsetminus S </tex>, который получается удалением элементов множества <tex> S </tex> из <tex> G </tex>.
+<tex> S </tex> разделяет <tex> u </tex> и <tex> v </tex>, если <tex> u </tex> и <tex> v </tex> принадлежат разным компонентам связности графа <tex> G \setminus S </tex>, который получается удалением элементов множества <tex> S </tex> из <tex> G </tex>.
 Из теоремы [[Теорема Менгера, альтернативное доказательство|теоремы Менгера для вершинной <tex>k</tex>-связности]] имеем, что наименьшее число вершин, разделяющих две несмежные вершины <tex> u </tex> и <tex> v </tex>, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих <tex> u </tex> и <tex> v </tex>.
@@ Строка 43: / Строка 43: @@
 * [[Теорема Менгера]]
 * [[Теорема Менгера, альтернативное доказательство]]
-==Литература==
 * Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
 * Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966
 [[Категория:Алгоритмы и структуры данных]]
 [[Категория:Связность в графах]]
 {{Заголовок со строчной буквы}}

@@ Строка 6: / Строка 6: @@
 [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Вершинной связностью]] графа называется
-<tex> \varkappa (G) = \max  \{ k  |  G </tex> вершинно  <tex>k</tex>-связен  <tex> \} </tex>, при этом для полного графа полагаем <tex> \varkappa (K_n) = n - 1 </tex>.
+<tex> \varkappa (G) = \max  \{ k \mid G </tex> вершинно  <tex>k</tex>-связен  <tex> \} </tex>, при этом для полного графа полагаем <tex> \varkappa (K_n) = n - 1 </tex>.
 {{Определение
@@ Строка 13: / Строка 13: @@
 }}
-[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью]] графа называется <tex> \lambda(G) = \max \{ l | G </tex> реберно <tex>l</tex>-связен <tex> \} </tex>, для тривиального графа считаем <tex> \lambda (K_1) = 0 </tex>.
+[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью]] графа называется <tex> \lambda(G) = \max \{ l \mid G </tex> реберно <tex>l</tex>-связен <tex> \} </tex>, для тривиального графа считаем <tex> \lambda (K_1) = 0 </tex>.

← Предыдущая		Версия 01:24, 25 декабря 2011
Строка 49:		Строка 49:
	* Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966		* Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966
	[[Категория:Связность в графах]]		[[Категория:Связность в графах]]
		+	{{Заголовок со строчной буквы}}

@@ Строка 1: / Строка 1: @@
-Связность - одна из топологических характеристик графа.
+<tex>k</tex>-cвязность - одна из топологических характеристик графа.
 {{Определение
 |definition=
@@ Строка 6: / Строка 6: @@
 [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Вершинной связностью]] графа называется
-<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>.
 {{Определение
@@ Строка 15: / Строка 13: @@
 }}
-[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью]] графа называется <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> \lambda (K_1) = 0 </tex>.
-Рассмотрим граф <tex> G </tex> .
+==k-связность и непересекающиеся пути между вершинами==
 Пусть <tex> S </tex> - множество вершин/ребер/вершин и ребер.
 <tex> S </tex> разделяет <tex> u </tex> и <tex> v </tex>, если <tex> u </tex> и <tex> v </tex> принадлежат разным компонентам связности графа <tex> G \smallsetminus S </tex>, который получается удалением элементов множества <tex> S </tex> из <tex> G </tex>.
-Справедливы следующие утверждения:
+Отсюда непосредственно следует:
 {{Утверждение