k-связность

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

[math]k[/math]-cвязность — одна из топологических характеристик графа.

Определение:

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

Вершинной связностью графа называется [math] \varkappa (G) = \max \{ k \mid 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 \mid G [/math] реберно [math]l[/math]-связен [math] \} [/math], для тривиального графа считаем [math] \lambda (K_1) = 0 [/math].

k-связность и непересекающиеся пути между вершинами

Рассмотрим граф [math] G [/math] и вершины [math] u [/math] и [math] v [/math].

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

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

Из теоремы теоремы Менгера для вершинной [math]k[/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]k[/math]-связности следует:

Утверждение:

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

См. также

• Теорема Менгера
• Теорема Менгера, альтернативное доказательство

Источники информации

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