Основы теории графов

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра компьютерных систем в управлении и проектировании (КСУП)

Основы теории графов

Отчёт к лабораторной работе №1

по дисциплине

«Дискретная математика»

Студент гр. 581-2

_______Раздобреева К.Г.

__________

Преподаватель

________ Жигалова Е.Ф.

__________

СОДЕРЖАНИЕ

Индивидуальная работа. Вариант № 5 4

Задание № 1 5

Задание № 2 6

Задание № 3 8

Задание № 4 9

Задание № 5 10

Задание № 6 11

Задание № 7

Цель лабораторной работы

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

Задание на лабораторную работу №1

1. Построить матрицы смежности и инциденций для графа своего варианта (рисунок 1).

2. По матрицам, представленным на рисунках 2,3, построить графы, предварительно определив их тип в терминах теории графов. Дать классификационное описание построенных графов.

3. Построить части графа (рисунок 1).

4. Выполнить бинарные операции над графами ( , ∩,). Для примеров взять к-л подграфы из графа своего варианта (рис.1).

5. Определить число маршрутов длины L= 3 для каждой пары вершин графа своего варианта.

6. Построить все маршруты длины L = 3 между вершинами,

указанным преподавателем.

7. Построить метрику графа своего варианта (рис.1).. Определить радиус, диаметр графа, периферийные и центральные вершины.

8. Оформить отчёт по результатам выполненной лабораторной работы.

Индивидуальная работа. Вариант № 5

Рис.2

Рис. 3

Задание № 1

Построить матрицы смежности и инциденций для графа своего варианта (рисунок 1).

Теория.

Матрица R=r[i,j] называется матрицей смежности, если её элементы образуются по правилу:

r[i,j]=1 ,если вершина x_i соединена с x_j ребром, т.е. x_i смежна x_j;

r[i,j]=0 в противном случае.

Для мультиграфа и смешанного графа задают:

r[i,j]=p если вершина x_i соединена с вершиной x_j p рёбрами;

r[i,j]=0 в противном случае.

Матрица, строки которой соответствуют вершинам графа, а столбцы - рёбрам, называется матрицей инциденций.

Матрица смежности

Матрица инциденций

Задание № 2

Определить тип матриц, представленных на рисунках 2,3, в терминах теории графов. Построить диаграммы графов по данным матрицам. Дать классификационное описание построенных графов.

Матрица № 1: (по рис2)

Тип матрицы: матрица смежности;

Диаграмма:

Классификационное описание: неориентированный, конечный, смешанный мультиграф.

Матрица № 2: (по рис3)

Тип матрицы: матрица инциденций;

Диаграмма:

Классификационное описание: неориентированный, конечный, смешанный мультиграф.

Задание № 3

Привести примеры частей графа своего варианта (рис. 1).