Примеры решений задач по теории графов

Задача 1. Постройте граф отношения "x+y ≤7" на множестве М={1,2,3,4,5,6}. Определите его свойства.

Посмотреть решение (pdf, 134 Кб)

Задача 2. Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Постройте дерево кратчайших путей.

Посмотреть решение (pdf, 196 Кб)

Задача 3. Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок) Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока. Источник – вершина 1, сток – вершина 8.

Посмотреть решение (pdf, 282 Кб)

Задача 4. Постройте остовное дерево минимального веса, используя алгоритмы Прима и Краскала. С помощью матрицы Кирхгоффа найдите количество (неизоморфных) остовных деревьев, используя пакеты компьютерной математики (например, MathCAD, Mathematica, MatLab).

Посмотреть решение (pdf, 173 Кб)