Некоторые задачи теории графов

· Проблема семи мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.

· Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)).

· Задача коммивояжёра — одна из наиболее известных NP-полных задач.

· Задача о клике — ещё одна NP-полная задача.

· Нахождение минимального стягивающего (остовного) дерева.

· Изоморфизм графов — можно ли путем перенумерации вершин одного графа получить другой.

· Планарность графа — можно ли изобразить граф на плоскости без пересечений ребер (или с минимальным числом слоев, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).

К теории графов также относится целый ряд математических проблем, не решенных на сегодняшний день.

Применение теории графов

· В химии (для описания структур, путей сложных реакций^[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемо информатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.

· В информатике и программировании (граф-схема алгоритма)

· В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.

· В экономике

· В логистике

· В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф) ^[2].