· Проблема семи мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.
· Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)).
· Задача коммивояжёра — одна из наиболее известных NP-полных задач.
· Задача о клике — ещё одна NP-полная задача.
· Нахождение минимального стягивающего (остовного) дерева.
· Изоморфизм графов — можно ли путем перенумерации вершин одного графа получить другой.
· Планарность графа — можно ли изобразить граф на плоскости без пересечений ребер (или с минимальным числом слоев, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).
К теории графов также относится целый ряд математических проблем, не решенных на сегодняшний день.
Применение теории графов
· В химии (для описания структур, путей сложных реакций[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемо информатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
|
|
· В информатике и программировании (граф-схема алгоритма)
· В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
· В экономике
· В логистике
· В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф) [2].