Индивидуальное домашнее задание по теории графов
Вариант 17
1. Найти с помощью алгоритма Дейкстры минимальный путь от вершины 
к вершине 
в орграфе, заданном весовой матрицей 
:
|
|
|
|
|
|
|
|
| ― | ― | ― | ||||
| ― | ― | |||||
| ― | ― | ― | ― | ― | ||
| ― | ― | ― | ― | |||
| ― | ― | ― | ― | ― | ||
| ― | ― | ― | ― | |||
| ― | ― | ― | ― | ― | ― | ― |
2. Найти с помощью алгоритма Беллмана-Мура минимальный путь от вершины к вершине 
в орграфе, заданном весовой матрицей :
|
|
|
|
|
|
|
| ― |
| ― | |||
| ― | ― |
| ― | ||
| ― | ― | ― | ― | ||
| ― | ― |
| ― |
| |
| ― |
| ― | ― | ― | |
| ― | ― | ― | ― | ― | ― |
3. Найти максимальный путь от вершины к вершине 
в орграфе, заданном весовой матрицей :
|
|
|
|
|
|
|
|
|
| ― | ― | ― | |||||
| ― | ― | ― | ― | ― | ― | ― | |
| ― | ― | ― | ― | ― | ― | ||
| ― | ― | ― | ― | ― | ― | ||
| ― | ― | ― | ― | ― | ― | ||
| ― | ― | ― | ― | ― | |||
| ― | ― | ― | ― | ― | |||
| ― | ― | ― | ― | ― | ― | ― | ― |
4. Построить с помощью алгоритма Прима минимальный остов графа, заданного весовой матрицей :
|
|
|
|
|
|
|
| ― | |||||
| ― | |||||
| ― | |||||
| ― | |||||
| ― | |||||
| ― |
Дата добавления: 2015-09-29; просмотров: 16 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| Про мисливське господарство та полювання | | | Школа молодого ресторатора |
