Решение. 1 страница

В графе присутствуют все вершины и все дуги графов и . Так же, как в объединении множеств, повторяющиеся элементы используем один раз.

В графе присутствуют те вершины и те дуги графов и , которые есть и в графе и в графе . На рисунке 7 изображены результаты объединения и пересечения графов и .

Матрица смежности результирующего графа образуется поэлементным логическим сложением матриц смежности графов и .

Матрица смежности результирующего графа образуется поэлементным логическим умножением матриц смежности графов и .

Рисунок 7 – Объединение и пересечение графов и

Композиция графов строится следующим образом: выписываются все дуги графа и соответствующие им дуги графа , в результирующий граф включаются дуги , исключая повторяющиеся (в данном случае, дуга (1,3)):

(1,1)	(1,3)	(1,3)
(1,1)	(1,4)	(1,4)
(1,2)	(2,1)	(1,1)
	(2,3)	(1,3)
(2,3)	–
(2,4)	(4,3)	(2,3)
(4,3)	–

Граф изображен на рис. 8. Матрица смежности графа получается умножением матрицы смежности графа на матрицу смежности графа .

Рисунок 8 – Граф

Композиция графов строится следующим образом: выписываются все дуги графа и соответствующие им дуги графа , в результирующий граф включаются дуги :

(1,3)	–
(1,4)	(4,3)	(1,3)
(2,1)	(1,1)	(2,1)
	(1,2)	(2,2)
(4,3)	–

Результирующий граф изображен на рис. 9. Матрица смежности графа получается умножением матрицы смежности графа на матрицу смежности графа .

Рисунок 9 – Граф

Операция композиции не является коммутативной, графы и не изоморфны.

Задача 1. Определить число компонент связности в графе , если задан следующим образом:

1)

2)

3)

Решение. 1) Граф имеет три компоненты связности. В первую входят вершины , во вторую – , в третью – , так как вершины первой компоненты нельзя соединить цепью с вершинами компонент два и три, а вершины компонент два и три также нельзя соединить цепью.

2) Граф имеет две компоненты связности, в первую входят вершины , во вторую – .

3) Граф имеет четыре компоненты связности. В первую входят вершины , во вторую – , в третью – , в четвертую – .

Задача 2. Найти в графе все точки сочленения и мосты, если :

Решение. Последовательно рассматриваем ребра графа, мысленно удаляя их из графа, только удаление ребра приводит к увеличению числа компонент связности, следовательно, является мостом. Аналогично поступаем с вершинами графа, и находим, что вершины 3 и 5 являются точками сочленения, так как удаление их из графа приводит к увеличению компонент связности.

Задача 3. Для графа найти расстояние от точки до всех вершин графа , где :

Решение. Расстояние от точки будем искать согласно алгоритма.

1. ,

2. ,

3. , просмотрели все вершины графа, отсюда , .

Задача 4. Найти расстояние от заданной точки до заданной точки и найти все геодезические цепи , если граф задан следующим образом:

Решение. 1. , 2. , 3. , 4. . Следовательно, . Геодезические цепи : ; ; ; .

Задание 7. Найти Эйлерову цепь в неориентированном графе , изображенном на рис. 10.

Решение. Прежде, чем приступать к нахождению Эйлеровой цепи, необходимо проверить степени вершин графа − согласно утверждению, для существования Эйлеровой цепи, необходимо и достаточно, чтобы в графе ровно 2 вершины нечетной степени.

Рисунок 10.

В рассматриваемом графе нечетные степени имеют вершины и (степень этих вершин равна 3). Соединяя эти вершины фиктивным ребром так, как показано на рис. 11, получаем граф :

Рисунок 11.

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

Пусть цикл составят ребра, проходящие через следующие вершины: . Согласно алгоритму, удаляем из все ребра, задействованные в цикле . Теперь граф будет таким, как показано на рис. 12.

Составляем следующий цикл : . Граф после удаления ребер, составляющих цикл , изображен на рис. 13.

Рисунок 12	Рисунок 13

Очевидно, что последний цикл будет состоять из v ₃ v ₅ v ₁| v ₃, где последнее ребро, соединяющее вершины и – фиктивно. После удаления ребер, составляющих цикл , в графе G ¢ не останется ни одного ребра.

Теперь по общим вершинам склеиваем полученные циклы. Поскольку и имеют общую вершину , то, объединяя их, получим следующий цикл: . Теперь склеим получившийся цикл с циклом : . Удаляя фиктивное ребро, получаем искомую Эйлерову цепь: .

Задание 8. Установить изоморфность графов G₁ и G₂, приведенных на рис. 14.

Рисунок 14.

Запишем элементы и с соответствующими им парами и определим частичную подстановку, проведя ребра 1 и 2, показанные на рис. 15. Затем последовательно строим ребра 3-7, используя отображения и и частичные подстановки. В результате получаем подстановку

которая удовлетворяет условию: для каждой вершины из существует вершина из , для которой и и существует подстановка, переводящая граф в граф . Следовательно, графы и изоморфны.

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

Рисунок 15.

Задание 9. Найти эксцентриситеты каждой вершины графа (рис. 16), радиус графа, его диаметр, центр, окружение и обхват.

Рисунок 16.

Решение. Эксцентриситет – наименьшее расстояние от вершины до наиболее удаленной от нее вершины графа. Диаметр – наибольший из эксцентриситетов, радиус – наименьший. Окружение – длина наименьшего простого цикла графа, обхват – длина наибольшего простого цикла. Центр находится в вершине (вершинах), на которых достигается минимальный эксцентриситет. Таким образом, для графа :

; ; ; центр графа – вершина 4. Окружение, как и обхват равны 3 (в графе всего один цикл).

Задание_____. Найти в графе гамильтонов цикл.

Задание 11. В графе (рис. ____) найти компоненты сильной связности.

Рисунок ___.

Решение. Компонента сильной связности ориентированного графа – это

Задание 12. Найти хроматическое число графа (рис. ___).

Рисунок ___.

Решение. 1. Вычисляем степени всех вершин графа .

2. Просматриваем все вершины графа в порядке невозрастания степеней.

3. Окрашиваем в цвет №1 все неокрашенные вершины, не смежные с вершинами, уже окрашенными в цвет №1.

Рисунок ___.

4. Окрашиваем в цвет №2 все неокрашенные вершины, не смежные с вершинами, уже окрашенными в цвет №2.

Рисунок ___.

5. Окрашиваем в цвет №1 все неокрашенные вершины, не смежные с вершинами, уже окрашенными в цвет №1.

Рисунок ___.

Задание 13. Используя алгоритм Дейкстры, в графе найти кратчайшие расстояния от вершины 1 до всех остальных вершин.

Рисунок ___ – Граф

Решение. Строим таблицу (см. лекции). На первом шаге присваиваем вершине 1 метку 0^*, а всем остальным вершинам – . .

	0^*

На втором шаге выписываем во второй столбец временные метки вершин (соответствующие весу дуги), в которые из 1-й вершины ведет дуга. Если дуги из вершины 1 нет, оставляем метку .

.

;

;

.

Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 2.

.

	0^*
		6^*

Третий шаг: проделываем все операции для вершины 2:

.

;

;

.

Метки для остальных вершин оставляем прежними.

Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 3.

.

	0^*
		6^*
			7^*

Дата добавления: 2014-11-20