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: Корень дерева- вершина . Все остальные вершины являются его узлами. Вершины - листы дерева. Путь .