Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow Дискретная математика. Сборник задач

Подсчет количества компонент связности у неориентированных графов

Теоретические сведения

Конечная последовательность ребер вида {у0, V,}, {у1? г2}, •••> {гт_1, г} называется простой незамкнутой цепью, если все вершины

у0, V,, у2, у,„ различны. Неориентированный граф С называется

связным, если для любых двух различных вершин У( и у2 существует простая незамкнутая цепь из V] в у2. Любой граф можно разбить на непересекающиеся связные графы, называемые компонентами или компонентами связности графа (7. Внутри каждой компоненты будет выполняться определение связности графа. Таким образом, несвязный граф имеет более одной (две или больше) компоненты. Связный граф всегда, по определению, состоит из одной компоненты.

Если в графе С = (V, II) п вершин и т ребер, тогда в нем не менее (я - т) связных компонент. Если при этом в С нет циклов, то граф состоит ровно из (л - т) связных компонент. Из этого следует, что если т < л - 2, то любой граф с л вершинами и т ребрами несвязен. Очевидно, что связный граф представляет собой простой цикл тогда и только тогда, когда каждая вершина имеет степень 2.

Задачи

Задача 2.21. Сколько может быть компонент связности у регулярного графа на девяти вершинах степени 2?

Решение.

Задачи на определение числа компонент связности удобно решать, начиная с оценки снизу. Сначала определимся с количеством ребер в исходном графе, оно равняется половине суммарной степени всех вершин, т.е. 9. Если все вершины имеют степень 2, это один простой цикл или несколько простых циклов. Получили, что данный граф может быть и связен.

Далее задача решается полным перебором возможных вариантов: один цикл, два цикла, три цикла. Больше трех циклов на девяти вершинах построить нельзя. Наихудшим с точки зрения связности является случай, представленный на рис. 2.6.

Решение задачи 2.21

Рис. 2.6. Решение задачи 2.21

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

Решение задачи 2.21 (окончание)

Рис. 2.7. Решение задачи 2.21 (окончание)

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

Пример связного графа, т.е. графа с числом компонент связности, равным единице, достаточно очевиден — он представляет собой простой цикл на девяти вершинах.

Ответ. Число компонент связности может быть равно 3, 2 или 1.

Задача 2.22. Чему равно число вершин, ребер и компонент связности у графа, полученного в результате выполнения следующих операций при отсутствии общих вершин?

  • а) Кь + С10;
  • б) и К,7;
  • в) С12 + Къв
  • г) (С, и Сд) + (73,

где (/] — К9, у которого удалили восемь ребер, имеющих одну общую вершину; (72К7, у которого удалили три ребра, образующих цикл; (73Рь, к которому добавили три попарно несмежных ребра. Черта наверху обозначает дополнение указанного графа.

Решение.

Решение такого рода задач удобнее всего демонстрировать в виде таблиц, так как заполнение каждой отдельной клетки, по сути, является очевидным. Для заданий а), б), в), г) решения и ответы даны в табл. 2.5—2.8.

Задача 2.23. Чему равно число компонент связности у графа, полученного в результате сложения полного графа на шести вершинах и простого цикла на восьми вершинах (общих вершин нет)?

Задача 2.24. Чему равно число компонент связности у графа, полученного в результате сложения регулярного графа на шести вершинах и простого цикла на десяти вершинах (общих вершин нет)?

Задача 2.25. Чему равно число компонент связности у графа, полученного в результате сложения пустого графа на пяти вершинах и пустого графа на десяти вершинах (общих вершин нет)?

Решение задачи 2.22, а

*6

Со

*6 + С,о

п

6

10

16

т

15

10

85

к

1

1

1

Таблица 2.6

Решение задачи 2.22,6

*5.8

*5.8

*7

*5.8 и К7

п

13

7

13

20

т

40

21

38

59

к

1

1

2

3

Таблица 2.7

Решение задачи 2.22, в

С2

Сі 2

*3,6

<42+*3.6

п

12

12

9

21

т

12

54

18

180

к

1

1

1

1

Таблица 2.8

Решение задачи 2.22, г

С.

С2

С2

Сз

(71 и Є 2

((?! ^ Є2) + (7^

п

9

7

7

6

іб

22

т

28

18

3

3

31

130

к

2

1

5

3

7

1

Задача 2.26. Какое число компонент связности может быть у произвольного ациклического графа на десяти вершинах и девяти ребрах?

Задача 2.27. Какое число компонент связности может быть у графа на 16 вершинах и 15 ребрах?

Задача 2.28. Какое число компонент связности может быть у графа на четырех вершинах и двух ребрах?

Задача 2.29. Какое число компонент связности может быть у графа на пяти вершинах и трех ребрах?

Задача 2.30. Сколько может быть компонент связности у регулярного графа на 15 вершинах степени 4?

Задача 2.31. Граф имеет десять вершин, две из них со степенью 7. Сколько у него может быть компонент связности?

Задача 2.32. Граф имеет десять вершин, из них две вершины степени 5, две вершины степени 4, две вершины степени 3, две вершины степени 2, две вершины степени 1. Сколько компонент связности может быть у такого графа? Построить по одному варианту для каждого возможного значения количества компонент.

Задача 2.33. Какое максимальное число ребер имеет произвольный несвязный граф на семи вершинах?

Задача 2.34. Какое минимальное число ребер имеет граф на 17 вершинах при условии, что в нем три компоненты связности?

Задача 2.35. Какое минимальное число ребер имеет граф на 15 вершинах при условии, что в нем четыре компоненты связности?

Задача 2.36. Какое максимальное число ребер имеет ациклический связный граф на 17 вершинах?

Задача 2.37. Какое минимальное число ребер имеет дерево на 17 вершинах?

Задача 2.38. Какое минимальное число ребер имеет ациклический граф на 17 вершинах?

Задача 2.39. Какое минимальное число ребер надо удалить из графа, являющегося деревом на восьми вершинах, чтобы он стал ациклическим?

Задача 2.40. Какое минимальное число ребер надо удалить из полного графа на пяти вершинах, чтобы он стал ациклическим?

Задача 2.41. Какое минимальное число ребер надо удалить из регулярного графа степени 3 на 12 вершинах, чтобы он стал ациклическим?

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы