GED / semestr5 / Экзаменационные вопросы

Теоретические вопросы:

1. Определение графа, орграфа, неографа. Матрицы смежности и инциденций. Приведите примеры.

2. Мультиграф, мультиграфическое число. Матрицы смежности и инциденций. Приведите примеры.

3. Конечный граф, нуль-граф, полный граф. Локальная степень вершины, регулярный граф. Приведите примеры.

4. Подграф, суграф, дополнение до полного. Приведите примеры.

5. Объединение, пересечение графов. Приведите примеры.

6. Маршрут, цепь, цикл. Нахождение маршрутов заданной длины. Связность. Приведите примеры.

7. Эйлеров граф. Гамильтонов цикл. Условия существования, теремы. Приведите примеры.

8. Деревья, лес. Свойства. Приведите примеры.

9. Цикломатическое число. Метод Краскала. Приведите пример.

10. Метрика графа. Аксиомы Фреше. Матрица расстояний. Диаметр графа. Приведите примеры.

11. Координатная решетка. Матрица геометрии. Суммарная длина ребер. Приведите примеры.

12. Раскраска графов. Хроматическое число. Приведите примеры.

13. Граф Кенига. Полный двудольный граф. Внутренняя устойчивость. Приведите примеры.

14. Изоморфизм графов. Плоские и планарные графы. Приведите примеры.

15. Орграф. Матрица инциденций и смежности. Маршрут, путь, контур. Приведите примеры.

Практические задания.

1. Задан граф. Построить R, I, список смежности.

2. Задан граф списком смежности. Построить граф.

3. Задана матрица R, построить матрицу I.

4. Задана матрица I, построить матрицу R.

5. Задана матрица R1, R2, найти объединение R1 и R2.

6. Задана матрица R1, R2, найти пересечение R1 и R2.

7. Заданы два графа, построить их объединение.

8. Заданы два графа, построить их пересечение.

9. Приведите примеры: нульграфа, полного графа, подграфа, сурграфа, дополнения до полного для заданного графа.

10. Задан граф. Нарисовать двойственный ему граф.

11. Задан граф. Построить маршрут, цепь, цикл.

12. Задан граф. Будет ли он Эйлеровым? Построить максимальный цикл.

13. Задан граф (матрицей R). Построить гамильтонов цикл.

14. Задан граф. Найти минимальное покрывающее его дерево.

15. Для решетчатого графа найти расстояние между вершинами x5 и x27 при p=6, q=5.

16. Задан решетчатый граф. Построить матрицу геометрии. Найти сумму длин всех его проводников.

17. Задан граф (матрицей R). Построить плоский и планарный граф.

18. Нарисовать пример мультиграфа. Подсчитать мощность каждого множества.

19. Задан граф. Найти все простые цепи соединяющие вершины x1 и x7.

20. Постройте матрицу расстояний для графа заданного следующей матрицей смежности:

21. Раскрасить заданый граф.

22. Задан граф полный граф, K₄. Длины ребер 120, 180, 140, 100, 70, 110 соответственно. Решить задачу о коммивояжере (найти гамильтонов цикл с наименьшим весом).

23. Задан орграф. Построить матрицу инциденций и смежности.

24. Задан орграф. Найти все простые цепи идущие из вершины x2.

25. Найти максимальную пропускную способность транспортной сети заданной орграфом.