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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	G1	⌐G1	G2	⌐G2	G3	⌐G3	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 вершинах, у которого двунаправленными являются дуги, у которых сумма двух инцидентных вершин четная, а остальные дуги направлены от вершин с большим номером к вершинам с меньшим номером. Компоненты задать перечислением вершин, их образующих.