Теория графов
Изучает графы — множества вершин и рёбер. Основана Эйлером (1736, задача о мостах Кёнигсберга). Применяется в социальных сетях, логистике, биоинформатике.
Теория графов
Ориентированные графы
Рёбра имеют направление (дуги). Степени входа/выхода вершин. Применение: сети (интернет, дороги с односторонним движением), зависимости (таск-менеджеры). Алгоритмы: топологическая сортировка (Kahn, 1962), поиск сильно связных компонент (Tarjan, 1972).
Взвешенные графы
Рёбрам присвоены веса (стоимость, расстояние, время). Алгоритмы кратчайшего пути: Дейкстра (1956, O(V²)), Беллман-Форд (1958, отрицательные веса), Floyd-Warshall (все пары, 1962). Применение: GPS-навигация, сетевая маршрутизация.
Планарные графы
Можно нарисовать без пересечений рёбер. Теорема Эйлера: V − E + F = 2 (вершины − рёбра + грани). Полные графы K₅ и K₃,₃ непланарны (Понтрягин, 1927). Применение: схемы печатных плат (PCB), карты.
Эйлеровы и Гамильтоновы графы
Эйлеров путь проходит каждое ребро ровно раз (Кёнигсбергские мосты, 1736). Гамильтонов — каждую вершину. Проверка Эйлерова: O(E). Гамильтонова: NP-полная.
Раскраска графов
Минимальное число цветов для раскраски вершин без одноцветных соседей (хроматическое число). Теорема о четырёх красках (1976): плоский граф ≤ 4 цвета. NP-полная задача.