Санкт-Петербургский государственный технологический институт
(Технический университет)
Факультет: 4
Курс: 2
Группа: 4805
Дисциплина
«Дискретная математика»
Отчет по лабораторной работе №2
«Графы»
Вариант №6
Выполнил:
студент Нефтанов Д.А.
Санкт-Петербург
2011
Задание 1
Построить граф, состоящий из 3 изолированных компонент мощностью 5, 6 и 7 изолированных вершин. Во всём графе должно быть 2 истока, 2 стока, 3 висячие вершины, 3 регулярных вершины, три из которых имеют степени 2, 3, 4. Максимальная степень кратности дуг графа должна быть 5. В графе должно быть не меньше, чем 3 пары противоположных дуг.
В отчете представить построенный граф с выделением всех построенных элементов. Надписать полустепени исхода и захода для каждой вершины.
Вершины изолированных компонент:
1, 2, 3, 4, 5 (мощность 5)
6, 7, 8, 9, 10, 11 (мощность 6)
12, 13, 14, 15, 16, 17, 18 (мощность 7)
Изолированные вершины: 19, 20, 21
Вершины-истоки: 5, 12
Вершины-стоки: 16, 18
Висячие вершины: 5, 18
Регулярные вершины:
4 (мощность 2), 6 (мощность 4), 9 (мощность 3)
Пары противоположных дуг между вершинами:
1-3, 1-4, 2-4, 6-8, 6-9, 6-10.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
p+ |
2 |
2 |
2 |
2 |
0 |
4 |
2 |
3 |
3 |
1 |
1 |
0 |
1 |
1 |
2 |
2 |
1 |
1 |
0 |
0 |
0 |
p- |
3 |
1 |
1 |
2 |
1 |
4 |
1 |
1 |
3 |
3 |
2 |
3 |
1 |
1 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
Задание 3
Построить связанный граф из 18 вершин, содержащий 4 точек сочленения, и не содержащий висячих и изолированных вершин. Рассчитать ранги вершин этого графа.
В отчете представить построенный граф с выделенными точками сочленения и подписанными рангами каждой вершины.
Вершины 4, 7, 8 и 14 – точки сочленения.
Ранги элементов вычисляются по следующей формуле: Y= X + XX , где X - матрица достижимости графа, Y – матрица результата.
Матрица достижимости:
Матрица результата:
2 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
2 |
4 |
3 |
4 |
4 |
6 |
10 |
10 |
10 |
10 |
7 |
0 |
8 |
8 |
9 |
0 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
2 |
3 |
3 |
5 |
9 |
9 |
9 |
9 |
6 |
0 |
7 |
7 |
8 |
0 |
8 |
0 |
0 |
0 |
0 |
2 |
0 |
3 |
7 |
7 |
7 |
7 |
4 |
0 |
5 |
5 |
6 |
0 |
6 |
0 |
0 |
0 |
0 |
0 |
2 |
3 |
7 |
7 |
7 |
7 |
4 |
0 |
5 |
5 |
6 |
0 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
6 |
6 |
6 |
6 |
3 |
0 |
4 |
4 |
5 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
5 |
5 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
5 |
5 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
5 |
5 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
5 |
5 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
3 |
3 |
4 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
3 |
3 |
4 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
2 |
3 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
4 |
4 |
5 |
2 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
∑ = 512.
Т.к. ранг вершины графа равен отношению суммы элементов соответствующей строки к сумме элементов всей матрицы, то ранги вершин графа будут равны:
r 1 = 4/512 = 0.0078 r10 = 20/512 = 0.0391
r2 = 107/512 = 0.2089 r11 = 20/512 = 0.0391
r3 = 0/512 = 0 r12 = 16/512 = 0.0253
r4 = 87/512 = 0.1699 r13 = 16/512 = 0.0253
r5 = 59/512 = 0.1152 r14 = 10/512 = 0.0195
r6 = 59/512 = 0.1152 r15 = 0/512 = 0
r7 = 47/512 = 0.0917 r16 = 4/512 = 0.0078
r8 = 20/512 = 0.0391 r17 = 23/512 = 0.0449
r9 = 20/512 = 0.0391 r18 = 0/512 = 0