лабораторные работы / Саратовский государственный технический университет
.docxСаратовский государственный технический университет
Балаковский институт техники, технологии и управления
Кафедра «Высшая математика и механика»
РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА
по дискретной математике
Тема: Графы
Вариант №_
Выполнил студент группы_________
________________________________
Проверил_______________________
Балаково 201_
Цель работы:
Расчетно-графическая работа направлена на освоение базовых понятий теории графов: способы задания графа матрицами, метрические характеристики графа, упорядочивание вершин и дуг графа. Изучение и закрепление этого материала позволит студентам в дальнейшем решать оптимизационные задачи теории графов.
Задание:
Задание 1. Для графа под номером 1 построить матрицу смежностей вершин.
Задание 2. Для графа под номером 2 построить матрицу смежностей дуг и матрицу инциденций.
Задание 3. Для графа под номером 2(считать его неориентированным) вычислить метрические характеристики графа: найти эксцентриситеты вершин, радиус и диаметр графа, центральные и периферийные вершины, построить диаметральную цепь.
Задание 4. Для графа под номером 3 упорядочить вершины и дуги графа. Вершины упорядочить двумя способами: по алгоритму Фалкерсона и матричным.
Задание 1.
Задание 1. Для графа под номером 1 построить матрицу смежностей вершин.
|
|
Е1 |
Е2 |
Е3 |
Е4 |
Е5 |
Е6 |
|
Е1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
Е2 |
1 |
1 |
0 |
0 |
1 |
0 =Р |
|
Е3 |
1 |
0 |
0 |
2 |
0 |
0 |
|
Е4 |
0 |
0 |
2 |
0 |
2 |
1 |
|
Е5 |
0 |
1 |
0 |
2 |
0 |
1 |
|
Е6 |
0 |
0 |
0 |
1 |
1 |
0 |
Задание 2.
Задание 2. Для графа под номером 2 построить матрицу смежностей дуг и матрицу инциденций.
|
|
е1 |
е2 |
е3 |
е4 |
е5 |
е6 |
е7 |
е8 |
е9 |
е10 |
|
е1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
е2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
е3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 =Q |
|
е4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
е5 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
е6 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
е7 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
е8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
е9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
е10 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
е1 |
е2 |
е3 |
е4 |
е5 |
е6 |
е7 |
е8 |
е9 |
е10 |
|
Е1 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
-1 |
|
Е2 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
Е3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 =Q |
|
Е4 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
|
Е5 |
0 |
-1 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
|
Е6 |
0 |
0 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Е7 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Задание 3.
Задание 3. Для графа под номером 2(считать его неориентированным) вычислить метрические характеристики графа: найти эксцентриситеты вершин, радиус и диаметр графа, центральные и периферийные вершины, построить диаметральную цепь.
е(Е1)=3 е(Е2)=2 е(Е3)=3 е(Е4)=3 е(Е5)=2 е(Е6)=3
d(E1E2)=1 d(E2E1)=1 d(E3E1)=1 d(E4E1)=2 d(E5E1)=2 d(E6E1)=1
d(E1E3)=1 d(E2E3)=1 d(E3E2)=2 d(E4E2)=1 d(E5E2)=1 d(E6E2)=2
d(E1E4)=2 d(E2E4)=1 d(E3E4)=1 d(E4E3)=1 d(E5E3)=2 d(E6E3)=3
d(E1E5)=2 d(E2E5)=1 d(E3E5)=2 d(E4E5)=2 d(E5E4)=2 d(E6E4)=3
d(E1E6)=1 d(E2E6)=2 d(E3E6)=3 d(E4E6)=3 d(E5E6)=1 d(E6E5)=1
d(E1E7)=3 d(E2E7)=2 d(E3E7)=2 d(E4E7)=1 d(E5E7)=1 d(E6E7)=2
е(Е7)=3
d(E7E1)=3
d(E7E2)=2
d(E7E3)=3
d(E7E4)=1
d(E7E5)=1
d(E7E6)=2
Радиус графа r(E)=2, Диаметр d(E)=3
Центральные вершины: Е2,Е5.
Периферийные вершины: Е1,Е3,Е4,Е6,Е7.
Диаметральная цепь: Е3-Е2-Е4,Е6-Е5-Е7.
Задание 4.
Задание 4. Для графа под номером 3 упорядочить вершины и дуги графа. Вершины упорядочить двумя способами: по алгоритму Фалкерсона и матричным.
Графический способ:
Находим вершину в которую не входит не одна дуга. Это вершина Е2-вершина 1 группы. Из нее выходят дуги 1-й группы: е1,е2,е8. Отбрасываем 1-ую группу.
Получаем:
Аналогично находим вершину, в которую не входят дуги и убираем их.
2группа. Е6(е4,е5,е7)
Получаем:
3группа. Е1(е3) удаляем вершину и дугу. Получаем:
4 группа. Е3(е6,е9)
Матричный способ:
Матрица смежности вершин:
|
|
Е1 |
Е2 |
Е3 |
Е4 |
Е5 |
Е6 |
|
Е1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
Е2 |
1 |
0 |
1 |
0 |
0 |
1 |
|
Е3 |
0 |
0 |
0 |
1 |
1 |
0 |
|
Е4 |
0 |
0 |
0 |
0 |
1 |
0 |
|
Е5 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Е6 |
1 |
0 |
0 |
1 |
1 |
0 |
Столбец, в котором все нули вычеркиваем и строку с тем же номером. Вычеркиваем столбец Е2 и строку Е2.
Получим 1 группу:
|
|
Е1 |
Е3 |
Е4 |
Е5 |
Е6 |
|
Е1 |
0 |
1 |
0 |
0 |
0 |
|
Е3 |
0 |
0 |
1 |
1 |
0 |
|
Е4 |
0 |
0 |
0 |
1 |
0 |
|
Е5 |
0 |
0 |
0 |
0 |
0 |
|
Е6 |
1 |
0 |
1 |
1 |
0 |
По аналогии вычеркиваем столбец и строку Е6. 2 группа:
|
|
Е1 |
Е3 |
Е4 |
Е5 |
|
Е1 |
0 |
1 |
0 |
0 |
|
Е3 |
0 |
0 |
1 |
1 |
|
Е4 |
0 |
0 |
0 |
1 |
|
Е5 |
0 |
0 |
0 |
0 |
3 группа: Е1
|
|
Е3 |
Е4 |
Е5 |
|
Е3 |
0 |
1 |
1 |
|
Е4 |
0 |
0 |
1 |
|
Е5 |
0 |
0 |
0 |
4 группа:Е3
|
|
Е4 |
Е5 |
|
Е4 |
0 |
1 |
|
Е5 |
0 |
0 |
5 группа: Е4
|
|
Е5 |
|
Е5 |
0 |
Суммируем столбцы матрицы смежности вершин и результат записываем в таблицу в первую строку, и так для каждой группы.
|
|
Е1 |
Е2 |
Е3 |
Е4 |
Е5 |
Е6 |
|
V1 |
2 |
0 |
2 |
2 |
3 |
1 |
|
V2 |
1 |
- |
1 |
2 |
3 |
0 |
|
V3 |
0 |
- |
1 |
1 |
2 |
- |
|
V4 |
- |
- |
0 |
1 |
2 |
- |
|
V5 |
- |
- |
- |
0 |
1 |
- |
|
V6 |
- |
- |
- |
- |
0 |
- |
Граф с упорядоченными вершинами:
1гр
2гр 3гр 4гр
5гр 6гр 
Е2
Е6
Е1
Е3
Е4
Е5
Граф с упорядоченными дугами:
1гр
2гр 3гр 4гр
5гр 6гр
Е2
Е6
Е2
Е2
Е3
Е1
Е6
Е6
Е6
Е5
Е5
Е5
Е4
Е4
Е4
Е1
Е1
Е3
Е3
Е5
Е3
