Rivalry2

HTML Diff

2 added 2 removed

Original 2026-01-01

Modified 2026-02-26

1 В этом уроке мы разберемся со связными подграфами, а также узнаем, что произойдет, если связный заменить на двусвязный.

2 <h2>Определения и свойства связности в графах</h2>

3 Связность графа - это существование пути от любой вершины к любой другой. При этом некоторые графы более связны, чем другие. Например, дерево является минимально связным, потому что удаление любой вершины или ребра из дерева приводит к его разъединению. Обратный пример - это полный граф, потому что он очень хорошо связан.

4 Раз степень связанности может меняться, значит нам нужен способ ее измерить. Обычно смотрят, сколько вершин или ребер нужно удалить, чтобы разъединить граф.

5 Граф называется k-связным, если для его рассоединения нужно удалить не менее k вершин. Связность неполного графа G обозначается как k(G) - это минимальное число вершин, которые нужно удалить, чтобы граф был разомкнут.

6 Граф называется k-краевым связным, если для его рассоединения требуется удалить не менее k ребер. В этом случае связность графа G обозначается κак 0 (G) - это минимальное число ребер, которые нужно удалить, чтобы граф был разомкнут.

7 Связность полного графа K_n - это особый случай. По условию, k(K_n) = n - 1.

8 Есть разница между связностью k и k-связностью:

9 <ul><li>Граф со связностью 3 может быть односвязным, двусвязным и трехсвязным</li>

10 <li>Связность k говорит о максимальном k, при котором граф - k-связный</li>

11 <li>У несвязного графа связность равна 0</li>

12 - <li>Связность графа равна 1, когда у него есть разрезанная вершина и разрезанное ребро</li>

12 + <li>Связность графа равна 1, когда у него есть разрезанная вершина или разрезанное ребро</li>

13 <li>У двусвязного графа нет разрезанной вершины или разрезанного ребра</li>

14 </ul>Вот несколько примеров связности графов:

15 В примере выше delta - это обозначение минимальной степени в графе.

16 <h2>Доказательство теоремы</h2>

17 Докажем следующую теорему:

18 Для любого простого графа k≤ k * 0 ≤ delta

19 В этой теореме (k * 0) ≤ delta, потому что граф разомкнется, если удалить ребра, инцидентных вершине минимальной степени.

20 Покажем, что (k * 0) ≤ k:

21 <ul><li>Пусть E - минимальный набор ребер, удаление которых разбивает граф на две компоненты, S и T</li>

22 <li>Получается, что |E| = (k * 0)</li>

23 </ul>Может оказаться, что E состоит из всех ребер между S и T:

24 <ul><li>Значит, у E есть множество ребер</li>

25 <li>При этом |S|-|T| в сумме больше n-1</li>

26 <li>При этом n-1 ≥ k, где n - число вершин в графе</li>

27 <li>В противном случае существуют s in S и t in T, которые не смежные</li>

28 </ul>Рассмотрим множество, которое состоит из всех соседей s в T и всех соседей t в S. Если удалить вершины этого множества, то это разъединит граф, так как мы не сможем попасть из s в t. Поэтому у этого множеств размер не менее k.

29 С другой стороны, ребра между двумя половинами этого множества исходят из E, поэтому его размер не больше κ 0. Значит, мы получаем (k * 0) ≤ k.

30 Наглядное доказательство этой теоремы:

31 Также подграфы могут быть не просто связными, но и двухсвязными. Посмотрим, что получится из этого.

32 <h2>Блоки</h2>

33 Напомним, чтокомпонента графа- это максимально связный подграф. Если мы заменим "связный" на "двухсвязный", то получимблок- это максимальный двухсвязный подграф графа.

34 Это подграф, который не содержит разрезанных вершин. Если добавить к нему любые другие вершины, из-за этого появится разрезанная вершина.

35 Мы можем разбить граф вокруг его разрезанных вершин на блоки:

36 Это несколько напоминает разбиение графа на компоненты. Только вместо того, чтобы разбивать граф на максимально связные части, мы разбиваем его на максимально двухсвязные части. Это важно, так как многие проблемы с графами можно упростить, если разбить граф на блоки.

37 Например, хроматическое число графа - это максимальное из хроматических чисел его блоков. В приведенном выше графе хроматическое число равно трем, так как для блока треугольника требуется три цвета, а для остальных - два.

38 - В качестве других примеров можно привести число прямых деревьев в графе, равное произведению числа прямых деревьев в каждом блоке. Еще с блоками связаны планарные графы - такие, которые изобразить на плоскости без пересечений ребер не по вершинам. Планарность можно свести к блокам - граф планарен, когда все его блоки планарны.

38 + В качестве других примеров можно привести число остовных деревьев в графе, равное произведению числа остовных деревьев в каждом блоке. Еще с блоками связаны планарные графы - такие, которые изобразить на плоскости без пересечений ребер не по вершинам. Планарность можно свести к блокам - граф планарен, когда все его блоки планарны.

39 <h2>Выводы</h2>

40 В этом уроке мы разобрались со связными подграфами, а также узнали, что произойдет, если связный заменить на двусвязный. В таком случае мы получим блок, у которого нет разрезанных вершин, но если добавить новые вершины, то тогда разрезанные появятся.