Курсовая работа: Теория графов

Задание 1. Определить, является ли данный граф: 1- орграфом или неорграфом или смешанным (обосновать ответ и выполнить обратное преобразование);

• Граф смешанный т.к. имеет и ориентированные и неориентированные связи
• Преобразование в орграф:

Задание 2. Задать граф перечислением вершин (узлов) и ребер (дуг), матрицей инцидентности
Задание 3. Определить основные характеристики графа
Задание 4 Произвести вершинную и реберную раскраску графа с определением вершинного и реберного хроматического чисел.
Задание 5. Определить, является ли данный граф эйлеровым. Обосновать ответ. Указать, есть ли эйлеров цикл (применить алгоритм Флери для его определения). При получении отрицательного ответа на данный вопрос необходимо, применяя минимальное количество известных операций на графах, преобразовать данный граф до эйлерова
Задание 6 Определить, является ли данный граф гамильтоновым
Задание 8. С помощью алгоритма выделения минимального остовного дерева получить остов. Преобразовать граф к взвешенному графу
Задание 9. Упорядочить граф методами Фалкерсона и матричным. Построить порядковую функцию. Построить функцию Гранди
Задание 10
С помощью метода Магу определить вершинную независимость (внутреннюю устойчивость: максимальную, минимальную) и доминирование (внешнюю устойчивость: максимальную, минимальную). Определить ядро графа