Практическая работа по теме "Графы"

ГРАФЫ. ИССЛЕДОВАНИЕ ОТОБРАЖЕНИЙ И СВОЙСТВ БИНАРНЫХ ОТНОШЕНИЙ С ПОМОЩЬЮ ГРАФОВ

ЦЕЛЬ РАБОТЫ: научиться определять основные характеристики графов и решать задачи с их применением. Для выполнения работы необходимо знать основные понятия теории графов; необходимо уметь формулировать задачи логического характера и применять методы математической логики для их решения.

КРАТКАЯ ТЕОРИЯ И МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

Графом G = (V, X) называется пара двух конечных множеств: V – множества вершин и Х – множества ребер. Если у ребер не указано направление, то такой граф называется неориентированным, у ориентированного графа каждое ребро имеет направление.

Мультиграфом называется граф, содержащий кратные ребра.

Псевдографом называется граф, содержащий петли или/и кратные ребра.

Степенью вершины графа deg(V) называется количество ребер ей инцидентных.

Операции над графами:

1. Объединение графов включает все вершины и ребра, которые содержатся в исходных графах.

2. Пересечение графов включает только одинаковые вершины и ребра, которые содержатся в исходных графах.

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

4. Дополнение содержит те вершины и ребра, которые не хватает исходному графу до полного графа.

Эйлеровым графом называется граф, содержащий эйлеров цикл (цикл, содержащий все ребра графа только один раз).

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

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

• 1, если вершина инцидента ребру

• 0, если вершина не инцидентна ребру

• 2, если ребро является петлей.

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

• -1, если вершина является началом ребра

• 0, если вершина не инцидентна ребру

• 1, если вершина является концом ребра

• ±1, если ребро является петлей.

Матрицей смежности графа называется квадратная матрица с n элементам (по числу вершин), в которой могут быть следующие значения:

• 0, если между вершинами нет ребра

• λ, если между вершинами есть ребро с кратностью λ

Пример 1. Граф G = (V, Х) задан множеством вершин, где V = {1, 2, 3, 4, 5, 6, 7} и списком ребер Х = {(1, 2), (1, 2), (2, 2), (2, 3), (1, 3), (3, 1), (3, 4), (4, 6), (4, 5)}.

а) Постройте граф.

б) Укажите вид графа, наличие петель, изолированных вершин и кратных ребер.

в) Определите степень каждой вершины графа.

б) Постройте матрицу инцидентности.

г) Постройте матрицу смежности.

Пример 2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего маршрута из А в F.

Пример 1. Решение

а ) Соединим попарно вершины, инцидентные каждому из заданных ребер

б) Задан неориентированный псевдограф, имеющий две пары кратных ребер: {(1, 2)², (1, 3)²}

Граф имеет изолированную вершину 7 и петлю в вершине 2.

в) deg(1) = 4, deg(2) = 5, deg(3) = 4, deg(4) = 3, deg(5) = 1, deg(6) = 1, deg(7) = 0

г) матрица инцидентности

г) матрица смежности

Пример 2. Решение Изобразим с помощью графа данные таблицы. Точками обозначим населенные пункты. Там, где пункты соединены дорогой, там соединяем точки.

Нарисуем пути из пункта А в F. Начнем с конца, с пункта F.

Получим кратчайший путь AB-ВС-СE-EF = 2 + 1 + 4 + 2 = 9

ПОРЯДОК ВЫПОЛНЕНИЯ И ФОРМА ОТЧЕТНОСТИ

Задание 1. Граф G = (V, Х) задан множеством вершин, где V = {1, 2, 3, 4, 5, 6, 7} и списком ребер.

а) Постройте граф.

б) Укажите вид графа, наличие петель, изолированных вершин и кратных ребер.

в) Определите степень каждой вершины графа.

б) Постройте матрицу инцидентности.

г) Постройте матрицу смежности.

I вариант Х = {(2, 3), (4, 3), (7, 6), (7, 7), (7, 2), (6, 4), (2, 7), (6, 4)}

II вариант Х = {(4, 5), (6, 5), (7, 6), (7, 7), (7, 2), (6, 4), (2, 7), (6, 4)}

Задание 2. Даны два графа G₁ = (V₁, Х₁) и G₂ = (V₂, Х₂). Изобразите геометрически объединение графов пересечение графов и кольцевую сумму

I вариант II вариант

G₁ G₂ G₁ G₂

Задание 3. Изобразите дополнения графов:

I вариант II вариант

Задание 4. Решить задачу с помощью ориентированного графа:

I вариант. Из пункта А в пункт В выехали пять машин одной марки разного цвета: белая, чёрная, красная, синяя, зелёная. Чёрная едет впереди синей, зелёная – впереди белой, но позади синей, красная впереди чёрной. Какая машина едет первой и какая последней?

II вариант. Из Череповца в Вологду выехали пятеро велосипедистов: Белов, Чернов, Краснов, Смирнов и Захаров. Чернов едет впереди Смирнова. Захаров едет впереди Белова, но позади Смирнова. Краснов – впереди Чернова. Определите, в каком порядке едут велосипедисты.

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

I вариант II вариант

Задание 6. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего маршрута из А в F.

I вариант II вариант

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что называют графом?

2. Охарактеризуйте виды графов.

3. Какими способами можно задать граф?