Учебник по теории графов

Теория графов — это раздел математики, который занимается изучением взаимосвязей между различными объектами. Граф представляет собой набор различных вершин, также известных как узлы, и эти узлы связаны друг с другом ребрами. В этом уроке мы рассмотрели все темы теории графов, такие как характеристики, эйлеровы графы, плоские графы, специальные графы, деревья, пути в теории графов и т. д. Этот учебник по теории графов будет полезен для изучения концепции предмета вместе с применение теории графов в реальной жизни и в различных областях.

Основы теории графов

• Введение в график
• Основная терминология графа
• Типы графика
• Прогулки, тропы, дорожки и схемы
• Компоненты расстояния на графике
• Cut-Vertices и Cut-Edges
• Мост на графике
• Независимые наборы
• Алгоритмы кратчайшего пути [алгоритм Дийсктры]
• Применение теории графов
• Обход графа[DFS]
• Обход графа[BFS]

Дерево

• Характеристики деревьев
• Минимальное остовное дерево Прима
• Минимальное остовное дерево Крускала
• Коды Хаффмана
• Обход дерева
• Задача коммивояжера

Специальный график

• Двудольные графы
• Независимые наборы и покрытие

Эйлеровы графы

• Эйлеровы графы
• Графики Эйлера — алгоритм Флери
• Графики Эйлера — проблема китайского почтальона Гамильтон

Соответствие

• Сопоставление — базовое, идеальное, двудольное
• Алгоритмы приближения

Раскраски

• Хроматические числа, жадный алгоритм раскраски
• Краевая окраска

Планарный график

• Planar Graph — основы, тестирование планарности

Направленные графы

• Направленные графы — степень центральности
• Направленные графы — слабая связь
• Направленные графы — сильные компоненты
• Направленные графы — эйлеровы, ориентированные графы Гамильтона
• Направленные графы - алгоритм Тарьяна для поиска сильно связанного компонента
• Рукопожатие в графовой теореме

Теория групп

• Группы, подгруппы, полугруппы
• Изоморфизм, Гомоморфизм
• Автоморфизм
• Кольца, Целостные области, Поля