Примеры решения задач

Пример 1 Построить матрицу инцидентности гиперграфа Н = (Х Е) изображенного на рис 1731

Рис. 17.31. Гиперграф H

Граф, изображенный на рис. 17.31. можно задать следующей матрицей инцидентности

Вопросы для самоконтроля

1. Дайте определение гиперграфа.

2. Какие две вершины, либо два ребра гиперграфа считают смежными?

3. Как составляется матрица инцидентности гиперграфа?

4. Дайте определение цепи в гиперграфе.

5. Как составляется матрица смежности гиперграфа?

6. Каким образом для гиперграфа можно построить двойственный граф?

7. Какой гиперграф считается деревом?

8. Что такое раскраска гиперграфа?

9. Дайте определение двудольного графа Кенига.

10. Как строится двудольный граф Кенига?

Задания для самостоятельной работы

1. Приведите пример гиперграфа.

2. Для произвольного гиперграфа запишите матрицу инцидентости.

3. Для произвольного гиперграфа запишите матрицу смежности.

4. Для произвольного гиперграфа постройте двойственный граф.

5. Задайте произвольный гиперграф и покажите на нем примеры цепей различной длины.

6. Приведите примеры гиперграфов, являющихся деревьями.

7. Задайте произвольный гиперграф и постройте его раскраску.

8. Для произвольного гиперграфа постройте двудольный граф Кенига.

9. Составьте алгоритм задания матрицы смежности гиперграфа.

10. Составьте алгоритм задания матрицы инцидентности гиперграфа.

Тестовые задания к модулю 4

1. Множество линий, соединяющих любые пары вершин графа – это:

а) множество ребер,

2. множество вершин,

3. множество петель,

4. множество дуг,

5. множество элементов.

2. Совокупность вершин, смежных с вершиной x_i графа G – это:

1. cписок связности,

2. матрица инцидентности,

3. список смежности,

4. матрица связности,

5. матрица смежности.

3. Когда вершины x_i и x_j связаны между собой ребром u_ij, это означает следующее:

1. вершина x_i инцидента ребру u_ij,

2. вершина x_i смежна ребру u_ij,

3. вершина x_i смежна с вершиной x_j,

4. вершина x_i инцидента вершине x_j,

5. вершина x_i связана с ребром u_ij.

4. Когда два ребра инцидентны одной вершине x графа G, то справедливы высказывания:

1. вершина смежна с этими ребрами,

2. эти ребра смежны с вершиной x,

3. эти ребра смежны между собой,

4. вершина x инцидента этим ребрам,

5. ребра инциденты вершине x.

5. Когда ребро u_ij соединяет вершины x_i и x_j графа G, то справедливы высказывания:

• вершины x_i и x_j инцидентны ребру u_ij

• вершины x_i и x_j смежны с ребром u_ij,

• ребро u_ij смежно вершине x_j,

• вершина x_j инцидента вершине x_i,

• ребро u_ij смежно вершине x_i.

6. Граф, у которого всем вершинам соответствуют некоторые целые числа – это:

1. числовой граф,

2. целый граф,

3. помеченный граф,

4. строгий граф,

5. регулярный граф.

7. Мультичисло графа – это:

1. число ребер,

2. число вершин,

3. максимальное число ребер соединяющих две вершины,

4. число ребер соединяющих две вершины,

5. число циклов.

8. Пусть задан граф G = (X, U). При X =  и U = , можно сказать, что граф G – это:

1. мультиграф,

2. нуль-граф,

3. пустой граф,

4. полный граф,

5. регулярный граф.

9. Граф G = (X, U) в котором любые две вершины соединены ребром – это:

1. мультиграф,

2. нуль–граф,

3. пустой граф,

4. полный граф,

5. регулярный граф.

10. Граф G = (X, U) в котором вершины имеют одинаковую локальную степень – это:

1. мультиграф,

2. нуль–граф,

3. пустой граф,

4. полный граф,

5. регулярный граф.

11. Граф G’ = (X’, U’) полученный путем удаления из графа G = (X, U) некоторого числа вершин вместе с инцидентными им ребрами – это:

1. подграф,

2. разрез,

3. суграф,

4. дополнение,

5. блок.

12. Конечная последовательность ребер вида S = (x₀, x₁), (x₁, x₂), …, (x_k–1, x_k), где x₀ и x_k – соответственно начальная и конечная вершины, это:

1. маршрут,

2. цепь,

3. цикл,

4. простая цепь,

5. простой цикл.

13. Длиной маршрута в графе называется:

1. расстояние между начальной и конечной вершинами,

2. сумма стоимостей,

3. число ребер маршрута,

4. число вершин маршрута,

5. число вершин графа.

14. Для подсчета числа маршрутов длины n в графе необходимо выполнить следующие действия:

• возвести матрицу смежности графа в степень n,

• возвести матрицу инцидентности графа в степень n,

• перебрать возможные варианты,

• перемножить ребра,

• перемножить вершины.

15. Цикл, не содержащий повторяющихся вершин кроме первой и последней – это:

1. цепь,

2. цикл,

3. простая цепь,

4. простой цикл,

5. эйлеров цикл.

16. Две вершины графа G являются связными, если выполняются следующие условия:

1. существует ребро инцидентное этим вершинам,

2. существует маршрут, где эти вершины являются конечными,

3. вершины соединены n ребрами,

4. вершины являются смежными,

5. граф полный.

17. Граф, между любыми двумя вершинами которого можно построить маршрут – это:

1. связный граф,

2. регулярный граф,

3. полный граф,

4. смежностный граф,

5. простой граф.

18. Цикл, проходящий по всем ребрам графа один раз – это:

1. простой цикл,

2. полный цикл,

3. эйлеров цикл,

4. гамильтонов цикл,

5. фундаментальный цикл.

19. Задача нахождения в полном графе с весами на ребрах гамильтонова цикла, у которого сумма ребер минимальна, носит название:

• задача Петри,

• задача Дирака,

• задача коммивояжера,

• транспортная задача,

• задача о назначениях.

20. Начальная вершина графа T – это:

1. дерево,

2. лес,

3. ветвь,

4. кустарник,

5. корень.

21. Ребра, выходящие из начальной вершины графа T – это:

1. дерево,

2. лес,

3. ветви,

4. кустарник,

5. корни.

22. Число покрывающих деревьев в полном графе K₄ равно:

1. 4,

2. 8,

3. 16,

4. 2,

5. 32.

23. Для графа T, являющегося деревом, верны следующие утверждения:

• граф T имеет n – 1 ребро,

• граф T не содержит циклов,

• граф T не связен,

• любые две вершины графа T соединены единственным циклом,

• любые две вершины графа T соединены циклом.

24. Длина кратчайшей цепи, соединяющей вершины x_i и x_j графа G – это:

1. протяженность вершин,

2. удаление вершин,

3. расстояние между вершинами,

4. последовательность вершин,

5. удаленность вершин.

25. Наименьшее число ребер, которые нужно удалить из графа, чтобы он стал деревом – это:

1. цикломатическое число,

2. хроматическое число,

3. число внутренней устойчивости.

4. число внешней устойчивости,

5. число внутренней полноты.

26. Цикломатическое число определяется по формуле (G) = m – n + k, где m –число вершин графа G, n – число его ребер, а k – это

1. Число компонент связности

2. Число циклов

3. Число цепей

4. Число простых цепей

5. Число простых циклов

27. Разбиение множества вершин X на k непересекающихся классов таких, что внутри каждого класса не должно содержаться смежных вершин – это:

1. разрез графа,

2. сечение графа,

3. раскраска графа,

4. пересечение графа,

5. разбиение графа.

28. При раскраске графа одним цветом красятся вершины, отвечающие следующим требованиям:

1. они являются сильно связными,

2. они являются слабо связным,

3. они являются связными,

4. они являются не связными,

5. они являются частично связными.

29. Подмножество, любые две вершины которого являются не смежными, может называться:

1. внутренне устойчивое,

2. внешне устойчивое,

3. максимально внутренне устойчивое,

4. независимое,

5. полное.

30. Подмножество, вершины которого смежны со всеми остальными вершинами графа – это подмножество:

1. полное,

2. внутренне устойчивое,

3. внешне устойчивое,

4. независимое,

5. несвязное.

31. Для определения числа внешней устойчивости необходимо определить:

• мощность минимального внешне устойчивого подмножества,

• число внутренней устойчивости,

• число минимальных внешне устойчивых подмножеств,

• число внешне устойчивых подмножеств.

• число ребер графа.

32. Подмножество являющееся одновременно внутренне и внешне устойчивым – это

1. клика,

2. ядро,

3. доминирующее подмножество,

4. независимое подмножество,

5. базовое подмножество.