Теория графов
Граф и Анализ
Метод Шимбелла
Поиск маршрута
Точки сочленения
Дейкстра (отр. веса)
Сравнение алгоритмов
Поток
Лаб 4
Лаб 5
Кол-во вершин:
p (степени):
p (веса):
Ориентированный
Веса:
Положительные
Отрицательные
Смешанные
Сгенерировать
Сгенерировать DAG
Перегенерировать веса:
Положительные
Отрицательные
Смешанные
Перестроить граф:
Ориентированный
Неориентированный
Матрица смежности (невзвешенная)
Матрица весов
Анализ (Задание 2)
Длина пути (k):
Рассчитать
Матрица минимальных путей
Матрица максимальных путей
Из вершины:
В вершину:
Найти маршрут
Матрица смежности (маршрут выделен)
Найти точки сочленения
Матрица смежности (точки сочленения выделены)
Тип весов: (сначала сгенерируйте граф)
Из вершины:
В вершину:
Рассчитать Дейкстру
Таблица Дейкстры (по этапам)
Весовая матрица (путь выделен)
n от:
до:
шаг:
Запустить сравнение
Задание 1: Генерация сети
Исток:
Сток:
Макс. пропускная способность:
Макс. стоимость:
Сгенерировать сеть
Матрица пропускных способностей
Матрица стоимостей
Задание 2: Максимальный поток (Форд-Фалкерсон)
Найти макс. поток
Матрица потока
Задание 3: Поток минимальной стоимости
Найти мин. стоимость потока
Матрица потока (мин. стоимость)
Задание 1: Число остовных деревьев (теорема Кирхгофа)
Посчитать число остовных деревьев
Матрица Кирхгофа
Задание 2-c: МОД (алгоритм Прима) + код Прюфера
Построить МОД и закодировать
Матрица весов (рёбра МОД выделены зелёным)
Задание 3-f: Минимальное вершинное покрытие (2-приближение)
Применить к:
Исходный граф
МОД
Найти минимальное вершинное покрытие
Матрица смежности (вершины покрытия выделены)
Задание 1: Эйлеров цикл (алгоритм Флери)
Найти эйлеров цикл
Матрица смежности (рёбра эйлерова цикла выделены)
Задание 2: Фундаментальная система циклов
Построить ФСЦ (МОД + циклы)
Матрица весов МОД (нетрейные рёбра отмечены)
Задание 2 (продолжение): Симметричная разность
Индексы циклов (через запятую, с 0):
Вычислить симметричную разность