Главная > Самоучители > Теория графов

Теория графов

1. Решения нескольких задач по теории графов.
Описание: Решения некоторых заданий по теории графов:
Задать граф следующими способами: перечислением, матрицами смежности и инцидентности.
Определить следующие основные характеристики графа:
— число ребер и дуг,
— число вершин,
— коэффициент связности графа,
-степени всех вершин,
-цикломатическое число графа.
Определить, является ли данный граф:
— планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);
— двудольным графом ( обосновать ответ и, если необходимо, то достроить до двудольного графа);
— деревом ( обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева)
— псевдографом или мультиграфом, или простым графом ( обосновать ответ и выполнить необходимые преобразования)
Привести пример подграфа, частичного графа и частичного подграфа.
Провести реберную и вершинную раскраски графа с определением вершинного и реберного хроматического числа.
Обозначим цвета числами натурального ряда, номер рядом с каждой вершиной или связью будет обозначать цвет.

2. Пример решения задачи о нахождении кратчайшего пути алгоритмом Дейкстры.
Описание: Пример решения задачи о нахождении кратчайшего пути алгоритмом Дейкстры на неориентированном взвешенном графе.
3. Пример решения задачи о коммивояжере ( поиск минимального гамильтонова цикла).
Описание: Пример решения задачи о нахождении гамильтонова цикла на графе венгерским алгоритмом.
3. Пример нахождения максимального потока методом Форда—Фалкерсона.
Описание: Пример нахождения максимального потока методом Форда—Фалкерсона.
4. Пример построения матрицы метрики графа.
Описание: Пример построения матрицы метрики графа.
5. Пример раскраски графа по алгоритму Магу-Вейсмана.
Описание: Раскраска графа минимальным количеством цветов по метода Магу-Вейсмана, определение хроматического числа графа.
6. Определить число вершинного покрытия графа. Пример решения.
Описание: Определение минимального вершинного покрытия с применением алгоритма Магу-Вейсмана.