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

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