#Теория графов

Теория графов — раздел дискретной математики, изучающий свойства графов. Граф представляется как множество вершин (узлов), соединенных ребрами или дугами.

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кенигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Вот одно из применений теории графов: существующие или проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети и т. п. — как ребра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Теория графов востребована во многих областях: в химии, информатике, программировании, экономике, логистике, схемотехнике и пр.

Многие структуры, представляющие практический интерес в логике, информатике, математике и других науках, могут быть представлены графами. Например, строение любого интернет-ресурса можно смоделировать при помощи ориентированного графа, в котором вершины — это статьи, а дуги — гиперссылки. Вся сеть Интернет тоже граф.

Терминология теории графов до сих пор строго не определена. В частности, в одной из IT-монографий сказано: «В программистском мире нет единого мнения о том, какой из двух терминов — "граф" или "сеть" — использовать. Мы выбрали термин "сеть", так как он, по-видимому, чаще встречается в прикладных областях». Более того, теория графов содержит большое количество нерешенных проблем и пока не доказанных гипотез.

Изображение: AzaToth/Wikimedia Commons