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

1 Наименование работы: Способы задания графов. Характеристики графов.

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

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

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

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

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

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

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

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

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

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

 

1. Перечислите мультиграфы, простые графы, двудольные и полные графы. Назовите порядок каждого графа.

 

2. Найти степень вершин графа. Присутствуют ли у него висячие и изолированные вершины?

 

 

3. Найти полустепени исхода и захода для каждой из вершин графа. Присутствуют ли у него висячие и изолированные вершины?

 

 

4. Постройте для данных графов матрицы смежности вершин и дуг, матрицы инцидентности.

 

 

 

 

5. По заданной матрице вершин постройте граф, затем, произвольно пронумеруйте дуги и постройте для своего графа матрицу дуг.

 

 

6. Выполните следующие задания:

1) Для данного графа запишите пример незамкнутого маршрута, замкнутой цепи, простой цепи, цикла и контура.

2) Найти расстояние между вершинами 1 и 7, 2 и 5, 3 и 4, 2 и 4.

3) Найти эксцентриситеты всех вершин.

4) Определите диаметр и центр графа. Запишите номера переферийных вершин.

5) Определите центр графа.

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

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

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

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

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

1. Что называется графом?

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

3. Какие графы называются мультиграфом, простым графом и двудольным?

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

5. Способы задания графов?

6. Что такое маршрут, путь и контур?

7. Опишите метрические характеристики графа.

ПРИЛОЖЕНИЕ:

Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).

Обозначение: G=(S,U), где S- множество вершин графа, U- множество ребер.

Число вершин графа G=(S,U) называется его порядком.

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

Мультиграфом называется граф без петель.

Простым графом называется мультиграф без кратных ребер.

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

Пример 1: