Метрические характеристики графа.

Расстоянием между вершинами и называется длина кратчайшего маршрута соединяющего эти вершины и обозначается .

Эксцентриситетом вершины  называется величина, которая равна расстоянию от данной вершины до наиболее отдаленной от нее и обозначается .

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

Вершина  называется периферийной, если .

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

Вершина  называется центральной, если . Множество всех центральных вершин называется центром графа.

 

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

1 Наименование работы: Виды графов.

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

Формирование ОК 2,4,8; овладение знаниями и умениями, необходимыми для освоения ПК 3.4. (спец. 09.02.03.), ПК 1.1. (спец. 09.02.04.).

3 Подготовка к занятию: Повторите тему: «Теория графов».

4 Литература:

4.1 Учебное пособие по дисциплине «Теория вероятностей и математическая статистика», 2018.

4.2 Приложение к ПЗ №10.

5 Перечень необходимого оборудования и материалов:

5.1 Бланк для отчета.

5.2 Канцелярские принадлежности.

6 Задание на занятие:

1. Нарисуйте граф с семью вершинами и шестью ребрами, не имеющий ни одного цикла.

2. Нарисуйте связный граф с семью вершинами и шестью ребрами.

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

4. С помощью графа - дерева решите следующую задачу: В столовой на горячее можно заказать щуку, грибы и баранину, на гарнир – картофель и рис, а из напитков – чай и кофе. Сколько различных вариантов обедов можно составить из указанных блюд?

5. Найдите узлы ордерева изображенного на рисунке и его корень, укажите его листы, перечислите несколько ветвей этого дерева и назовите его высоту.

7 Порядок выполнения работы:

Выполните практическую работу в соответствии с заданиями (основная часть п.п. 6.1 – 6.5) и сдайте зачет).

8 Содержание отчета:

Решения задач в соответствии с заданием.

9 Контрольные вопросы:

1. Какой граф называется деревом?

2. Что такое Эйлеров граф?

3. Что такое гамильтонов граф?

4. Что называется лесом?

5. Перечислите основные характеристики дерева и дайте их определения.

ПРИЛОЖЕНИЕ:

Дерево - связный граф без циклов.

Связанный граф - если все его вершины связаны.

Лес (или ациклический граф) - неограф без циклов (может быть и несвязным).

Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:

· G - дерево;

· G - связный граф, содержащий n-1 ребро;

· G - ациклический граф, содержащий n-1 ребро;

· Любые две несовпадающие вершины графа G соединяет единственная цепь.

· G - ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.

Остов (каркас) связного графа - дерево, содержащее все вершины графа. Определяется неоднозначно.

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

Корень дерева- вершина с нулевой степенью захода.

Узел ордерева - вершина, отличная от корня.

Листом ордерева называется вершина , такая, что и .

Ветвью ордерева называется путь из корня в лист.

Высотой дерева является длина его наибольшей ветви.

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

Теорема: Граф G является эйлеровым тогда и только тогда, когда G – связный и все его вершины имеют четную степень.

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

Пример 1: Корень дерева- вершина . Все остальные вершины являются его узлами. Вершины - листы дерева. Путь .