Эти задания могут помочь при подготовке к экзамену.

Дан граф (для вопросов 1-12).

1. Построить матрицу смежности и матрицу инциденций для данного графа.

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

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

4. Построить матрицу базисных разрезов для данного графа и определить ранг графа.

5. Найти все пустые подграфы данного графа.

6. Определить число внутренней вершинной устойчивости данного графа.

7. Определить число внешней вершинной устойчивости данного графа.

8. Определить с достаточным обоснованием хроматическое число данного графа.

9. Определить с достаточным обоснованием хроматический класс данного графа.

10. Определить диаметр данного графа.

Раскраска графов

11. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) связного графа на 92 вершинах, цикломатическое число которого равно двум.

12. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) ациклического графа, в котором число компонент связности ровно в 5 раз меньше, чем ребер, а вершин – нечетное количество.

13. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) связного графа на 7 вершинах, имеющего 19 ребер.

14. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) связного двудольного графа на 12 вершинах, с долями имеющими нечетное число вершин.

Операции над графами. Знак ⌐ перед обозначением графа означает дополнение данного графа до полного. Для всех задач данного типа рекомендуется заполнить таблицу типа

	G₁	⌐G₁	G₂	⌐G₂	G₃	⌐G₃	1-ая операция	2-ая операция
n
m
k
γ
h
d

15. Вычислить диаметр, цикломатическое и хроматическое числа графа (G₁ U G₂) + G₃, где G₁ – простой цикл на 20 вершинах, G₂ – полный граф на 6 вершинах, у которого удалили три ребра, образующих цикл, G₃ – полный граф двудольный граф с долями 6 и 17, у которого удалили одно ребро. При этом графы G₁ и G₂ имеют ровно одну общую вершину.

16. Вычислить диаметр, цикломатическое и хроматическое числа графа (⌐G₁ + G₂) U ⌐G₃, где G₁ – полный граф на 9 вершинах, у которого удалили 5 ребер, образующих простой цикл, G₂ – полный граф на 13 вершинах, у которого удалили 5 ребер имеющих одну общую вершину, G₃ – простой цикл на 21 вершине. При этом графы не имеют общих вершин.

17. Вычислить диаметр, цикломатическое и хроматическое числа графа (G₁ + ⌐G₂) U ⌐G₃, где G₁ – простой цикл на 70 вершинах, G₂ – простой цикл на 6 вершинах, G₃ – полный двудольный граф с долями 15 и 8, у которого удалили одно ребро. При этом графы G₁ и G₂ имеют ровно одну общую вершину.

18. Вычислить диаметр, цикломатическое и хроматическое числа графа (G₁ U G₂) + ⌐G₃, где G₁ – полный двудольный граф с долями 7 и 9, у которого удалили одно ребро, G₂ – полный граф на 11 вершинах, у которого удалили 3 ребра, имеющих одну общую вершину, G₃ – простой цикл на 7 вершинах. При этом графы не имеют общих вершин.

19. Вычислить диаметр, цикломатическое и хроматическое числа графа (⌐G₁ U G₂) + ⌐G₃, где G₁ – простой цикл на 29 вершинах, G₂ – полный граф на 6 вершинах, G₃ – полный граф на 7 вершинах, у которого удалили 6 смежных ребер. При этом графы G₁ и G₂ имеют ровно одну общую вершину.

20. Вычислить диаметр, цикломатическое и хроматическое числа графа (G₁ + ⌐G₂) U G₃, где G₁ – полный граф на 9 вершинах, у которого удалили 5 ребер, образующих простой цикл, G₂ – полный граф на 13 вершинах, у которого удалили 5 ребер имеющих одну общую вершину, G₃ – простой цикл на 21 вершине. При этом графы не имеют общих вершин.

21. Вычислить диаметр, цикломатическое и хроматическое числа графа (⌐G₁ + G₂) U ⌐G₃, где G₁ – простой цикл на 70 вершинах, G₂ – простой цикл на 6 вершинах, G₃ – полный двудольный граф с долями 15 и 8, у которого удалили одно ребро. При этом графы G₁ и G₂ имеют ровно одну общую вершину.

22. Вычислить диаметр, цикломатическое и хроматическое числа графа (G₁ + ⌐G₂) U G₃, где G₁ – полный граф на 9 вершинах, у которого удалили 5 ребер, образующих простой цикл, G₂ – полный граф на 13 вершинах, у которого удалили 5 ребер имеющих одну общую вершину, G₃ – простой цикл на 21 вершине. При этом графы не имеют общих вершин.

23. Вычислить диаметр, цикломатическое и хроматическое числа графа (G₁ U ⌐G₂) + G₃, где G₁ – полный двудольный граф с долями 7 и 9, у которого удалили одно ребро, G₂ – полный граф на 11 вершинах, у которого удалили 3 ребра, имеющих одну общую вершину, G₃ – простой цикл на 7 вершинах. При этом графы не имеют общих вершин.

Построение графов

24. Построить связный двудольный граф на 14 вершинах со следующим распределением степеней вершин: 1 вершина степени 4, 3 вершины степени 3, 3 вершины степени 2 и 7 вершин степени 1 или дать обоснованный ответ о невозможности построения такого графа.

25. Построить связный граф на 13 вершинах, цикломатическое число которого равно двум, а распределение степеней вершин следующее: 5 вершин степени 3, 1 вершины степени 2 и 6 вершин степени 1 или дать обоснованный ответ о невозможности построения такого графа.

26. Построить произвольный граф на 7 вершинах, цикломатическое число которого равно 16, а все вершины имеют степень 6 или дать обоснованный ответ о невозможности построения такого графа.

27. Построить связный ациклический граф на 15 вершинах, а распределение степеней вершин следующее: 2 вершины степени 4, 1 вершины степени 3, 1 вершина степени 2 и 11 вершин степени 1 или дать обоснованный ответ о невозможности построения такого графа.

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

29. Построить или обосновать невозможность построения графа с 4 вершинами, 4 ребрами и двумя компонентами.

30. Построить или обосновать невозможность построения графа с 6 вершинами, 12 ребрами и двумя компонентами связности.

31. Построить или обосновать невозможность построения графа с 9 ребрами, 2 компонентами связности и цикломатическим числом равным 4.

32. Построить произвольный граф на 9 вершинах, который имеет следующее распределение степеней вершин:

ü одна вершина со степенью 4

ü две вершины со степенью 2

ü четыре вершины со степенью 3

ü Две вершины со степенью 1

или обосновать невозможность построения такого графа.

33. Построить произвольный граф на 8 вершинах, который имеет следующее распределение степеней вершин:

ü одна вершина со степенью 5

ü две вершины со степенью 3

ü три вершины со степенью 2

ü две вершины со степенью 1

или обосновать невозможность построения такого графа.

Диаметр графа

34. Определить с достаточным обоснованием, чему может быть равен диаметр (указать точную цифру или возможный диапазон значений) произвольного графа с цикломатическим числом равным 5, у которого ребер на 3 больше чем вершин.

35. Определить с достаточным обоснованием, чему может быть равен диаметр (указать точную цифру или возможный диапазон значений) графа, полученного в результате операции объединения двух графов, один из которых представляет собой простой цикл на 39 вершинах, а второй – полный граф на 9 вершинах. При этом два графа имеют ровно одну общую вершину.

Сильная связность

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

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