Кр
.pdf
1. |
Для неориентированного графа с вершинами ,,,,,,,, и ребрами |
= , = |
|||||
|
, = , = , = , = , = , |
= , |
= , |
= , |
= . |
||
|
а) указать число компонент связности; |
|
|
|
|
|
|
|
б) указать хроматическое число и соответствующую ему раскраску. |
|
|
||||
2. |
Для неориентированного графа из п. 1: |
|
|
|
|
|
|
|
а) указать цикломатическое число; |
|
|
|
|
|
|
|
б) построить базис циклов. |
|
|
|
|
|
|
3. |
0 |
1 |
1 |
0 |
1 |
|
|
|
1 |
0 |
0 |
0 |
1 |
|
|
|
а) Построить граф по матрице смежности = 1 |
0 |
0 |
0 |
2 . |
|
|
|
0 |
0 |
0 |
0 |
1 |
|
|
|
1 |
1 |
2 |
1 |
0 |
|
|
|
б) Для графа из пункта а) выписать матрицу инцидентности. |
|
|
|
|||
4.а) Нарисовать какое-нибудь корневое дерево с 11-ю вершинами и построить его бинарный код.
б) Построить дерево по коду [4 2 1 4 1 1 4 2].
5.Диаграмма графа состоит из вершин и ребер правильной шестиугольной призмы, в основаниях которой проведены по две главные диагонали. Выяснить, планарный ли этот граф (ответ обосновать).
6.а) Построить ориентированный граф по матрице инцидентности
0 |
−1 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
−1 |
0 |
0 |
|
= −1 0 |
0 |
0 |
−1 |
0 . |
||
1 |
1 |
0 |
1 |
0 |
0 |
|
0 |
0 |
−1 |
0 |
1 |
−1 |
|
б) Выписать матрицу смежности графа из п. а). |
|
|
|
|
||
7.Пусть – полный неориентированный граф с вершинами 1,2,3,4, к которому добавлены вершины 5 и 6, а также и ребра 26 и 45. Найти число остовов графа , а также изобразить диаграммы 3-х из них.
8.Пусть - основание взвешенного ориентированного графа (см. рис.). Поменяем на графе весовое отображение: заменим нечетные веса единицей, а четные – двойкой. Найти остов минимального веса в графе сновым весовым отображением. Указать его вес.
9.С помощью алгоритма Дейкстры найти расстояния от вершины s ориентированного графа(см. рис.) до остальных его вершин; указать кратчайший путь от вершины s до вершины t.
10.С помощью алгоритма Форда-Фалкерсона найти максимальный поток и минимальный разрез в сети (см. рис.) Вершина s – источник, вершина t – сток.
|
|
|
|
|
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
s |
|
|
|
|
|
1 |
|
|
|
|
|
3 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
3 |
|
b |
|
|
1 |
|
|
|
|
|
|
|
x |
|
|
6 |
|
|
|
||||
|
|
|
9 |
|
|
|
|
3 |
|
|
|
3 |
|
|
|
|
|
5 |
t |
|||||
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
y |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
с |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||