Контрольная работа по дисциплине «Теория графов и классические задачи прикладной математики в экономике»
Вариант № 7
1. Для неориентированного графа построить матрицу смежности и матрицу инцидентности.
Решение
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1:
|
|
|
|
|
| |
| 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 0 |
Матрицей инцидентности ориентированного (или неориентированного) графа 
с 
вершинами 
и 
ребрами 
называется матрица 
размера 
с элементами:
Таким образом, в матрице инцидентности 
любому ребру 
соответствует 
ый столбец, в котором в 
ой строке стоит 1, а в k-ой - 
. Ребра-петли выделяются числом 2.
|
|
|
|
|
| |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
2. Для орграфа построить матрицу смежности и матрицу инцидентности
Решение
Матрица смежности графа:
|
|
|
|
|
| |
| 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 |
Матрица инцидентности ориентированного графа
|
|
|
|
|
| |
| 1 | -1 | 0 | 0 | 0 | 0 |
| 1 | 0 | -1 | 0 | 0 | 0 |
| 1 | 0 | 0 | -1 | 0 | 0 |
| 1 | 0 | 0 | 0 | -1 | 0 |
| 0 | -1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | -1 | 0 | 0 |
| 0 | 0 | 1 | 0 | -1 | 0 |
| 0 | 0 | 0 | 1 | 0 | -1 |
| 0 | 0 | 0 | 0 | 1 | -1 |
3. Дана матрица смежности неориентированного графа. Построить граф.
|
|
|
|
|
| |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 |
4. Дана матрица инцидентности орграфа. Построить орграф.
|
|
|
|
|
|
|
|
| |
| -1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | -1 | -1 | 0 | 0 | 0 | 0 |
| 0 | 1 | -1 | 0 | 0 | -1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | -1 | -1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | -1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
Граф имеет 6 вершин и 9 ребер.
5. Дан неориентированный граф. Построить минимальное и максимальное остовные деревья и найти их веса.
Решение
Минимальное остовное дерево
Стоимость: 2+1+1+3+2+3+1+2+2+1+4=22
Максимальное остовное дерево:
Стоимость: 4+6+5+5+6+5+4+3+6+6+5=55.
Воспользуемся алгоритмом Краскала.
При построении минимального остовного дерева вводим в дерево ребра минимального веса 1и вершины: 2 и 5, 6, 8 и 11. Теперь вводим ребра веса 2, так, чтобы не образовать циклы. Вводим вершины 1, 3 и 7, 10 и 11, 12. Вводим в дерево ребра минимального веса 3. Вводим вершины 3, 4 . Вводим в дерево ребро минимального веса 4 и вершину 9. Все вершины включены в дерево.
Аналогично строится максимальное остовное дерево.
