Практическое занятие № 6

Пример.

.

Рис. 4

3. Для наглядности граф представляют в виде геометрического объекта: вершинам соответствуют различные выделенные точки в пространстве (на плоскости), ребрам – отрезки кривых, связывающие вершины.

Рассмотрим некоторые разновидности графов.

Неориентированный граф G = (V, E)– двудольный, если множество его вершин V можно разбить на два такие подмножества V ₁и V ₂, что каждое ребро имеет один конец в V ₁, а другой в V ₂. Если же каждая из вершин класса V ₁ связана ребром с каждой вершиной класса V ₂, то граф называется полным двудольным и обозначается К _m,n, где m =| V ₁|, n =| V ₂|. На рис. 5 а изображен двудольный граф, на рис. 5 б и 5 в – полные двудольные графы К _3,2 и К _3,3 .

Пример.

а б в

Рис. 5

Полным графом называется граф без кратных ребер (и иногда без петель), в котором любые две вершины соединены ребром (ориентированным или неориентированным). Полный неориентированный граф с n вершинами обозначается К_n. Очевидно, граф К_n содержит n (n - 1)/2 ребер.

На рис. 6 а, 6 б и 6 в изображены графы К ₃, К ₄, К ₅, соответственно. На рис. 6 г также изображен полный граф.

а б в г

Рис. 6

5.3. Подграфы

Граф G ¢ = (V ¢, E ¢) называется подграфом графа G = (V, Е), обозначение: G ¢ Í G, если V ¢ Í V, Е ¢ Í Е и для множеств V ' и Е' сохраняются инциденции графа G. При этом, очевидно, каждое ребро из Е ' входит в подграф G ¢ вместе со своими концами. Подграф называется собственным, если он отличен от самого графа.

Пример. Графы на рис. 7 б и 7 в являются подграфами графа на рис. 7 а.

а б в

Рис. 7

5.4. Изоморфизм графов

Два графа G ₁ = (V ₁, E ₁) и G ₂ = (V ₂, E ₂) изоморфны, если между их вершинами существует взаимно однозначное соответствие j: V ₁ ® V ₂ такое, что для любой пары вершин u, v из V ₁ ребро (u, v) Î Е₁ «ребро (j(u), j(v)) Î Е₂.

Пример. Графы, изображенные на рис. 8, являются изоморфными.

Рис. 8

Изоморфные графы отличаются только нумерацией вершин. Матрицы смежности двух изоморфных графов могут быть получены одна из другой перестановкой строк и столбцов. Чтобы узнать, являются ли два графа изоморфными, нужно произвести все возможные перестановки строк и столбцов матрицы смежности одного из графов. Если после какой-нибудь перестановки получится матрица смежности второго графа, то эти графы изоморфны. Чтобы убедиться, что графы неизоморфны, надо выполнить все n! возможных перестановок строк и столбцов.

5.5. Степени вершин графа

Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v. Вершина графа, имеющая степень 0, называется изолированной, а степень 1 – висячей.

В случае неориентированного псевдографа считается, что вклад каждой петли, инцидентной некоторой вершине v, в d(v) равен 2 (тогда как вклад любого другого ребра, инцидентного вершине v, равен 1).

Полустепенью исхода (захода) вершины v орграфа D называется число d⁺(v) (d^-(v)) дуг орграфа D, исходящих из вершины v (входящих в вершину v).

В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине v, в d(v) равен 1, как в d⁺(v), так и в d^-(v).

В графе G (рис. 3 б) степень вершины v ₁ равна четырем, т. е. d(v ₁) = 4; вершина v ₄ – висячая, так как d(v ₄) = 1. В ориентированном псевдографе (рис. 3 а) степень вершины v ₆ равна трем, т. е. d(v ₆) = d⁺(v ₆) + (d^-(v ₆) = 2 + 1 = 3; вершина v ₁ – висячая, так как d(v ₁) = 1, вершина v ₅ – изолированная, так как d(v ₅) = 0.

Задания

Для аудиторных занятий

1. Даны реализации графов (рис. 9). Какие это графы? Описать их основные характеристики. Привести примеры элементов графов.

а) б) в)

Рис. 9

2. Записать матрицы смежности и инцидентности для неориентированного графа (рис. 9 а).

3. Записать матрицы смежности и инцидентности для ориентированного графа (рис. 9 б).

4. Изобразить ассоциированный граф для заданного графа (рис. 9 б).

5. Изобразить все попарно неизоморфные 4-вершинные графы без петель и кратных ребер. Записать для них матрицы смежности и инцидентности.

6. Построить все попарно неизоморфные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин.

7. Какое из двух утверждений верно: а) ориентированный граф является частным случаем неориентированного графа; б) неориентированный граф является частным случаем ориентированного графа.

8. Перечислить все возможные способы задания графов.

9. Всегда ли матрица смежности симметрична относительно главной диагонали?

10. Как по матрице смежности определить число ребер неориентированного графа?

Для самостоятельной работы

1. Как по матрице инцидентности, не рисуя граф, определить его матрицу смежности?

2. Может ли матрица быть матрицей смежности неориентированного графа?

3. Какие из следующих утверждений являются правильными: а) если матрица смежности несимметричная, то граф ориентированный; б) если граф неориентированный, то матрица смежности симметричная; в) если диагональные элементы матрицы смежности – нули, то граф неориентированный?

4. Записать матрицы смежности и инцидентности для ориентированного графа (рис. 9 в).

5. Изобразить все попарно неизоморфные ориентированные псевдографы, содержащие: а) 2 вершины и 2 дуги; б) 3 вершины и 4 дуги; в) 4 вершины и 3 дуги.

6. Изобразить ассоциированный граф для заданного графа (рис. 9 в).

7. Чему равны степени вершин для ориентированного и неориентированного графов?

8. Определить степени вершин орграфа (рис. 3 а). Есть ли в заданном графе изолированные и висячие вершины?

9. Определить степени вершин в заданных графах (рис. 9).

10. Даны реализации графов (рис. 9). Какие это графы? Привести примеры смежных вершин и смежных ребер.

Литература

1. Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.

2. Нефедов, В. Н. Курс дискретной математики: учеб. пособие / В. Н. Нефедов, В. А. Осипова. – М.: Изд-во МАИ, 1992. – 264 с.

3. Акимов, О. Е. Дискретная математика. Логика, группы, графы. – 2-е изд., доп. / О. Е. Акимов. – М.: Лаборатория базовых знаний, 2001. – 367 с.

Тема: «Путь в графе. Поиск путей (маршрутов)»

Цель занятия:

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

Дата добавления: 2017-02-01