Теория графов. 
Решение задачи коммивояжера

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

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

G={R, V},.

где V есть подмножество любого счётного множества, а R — подмножество VЧV.

Рис. 1 Граф с шестью вершинами и семью рёбрами

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут (см. Рис. 1).

Терминология теории графов поныне не определена строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано «В программистском мире нет единого мнения о том, какой из двух терминов „граф“ или „сеть“. Мы выбрали термин „сеть“, так как он, по-видимому, чаще встречается в прикладных областях» Прилуцкий М. Х. Математические основы информатики. Нижний Новгород: Нижег.гос.ун-т, 2000. С. 21.