Библиография

Предмет: Теория графов

Тема: Программирование задач на графах. Гамильтоновы и эйлеровы цифры

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

Началом теории графов считается 1736 год, когда вышла в свет статья Эйлера с его знаменитыми рассуждениями о Кенигсбергских мостах. Затем около 100 лет эта статья оставалась единственной, а методы теории графов невостребованными практикой. Интерес к графам появился только в середине 19 века благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. С тех пор сфера применений теории графов непрерывно расширялась и сегодня она представляет собой мощную формальную систему, имеющую необозримое множество областей практического применения.

Теория графов получила широкое развитие с середины 50-х годов 20 века благодаря развитию вычислительной техники. Граф из-за его наглядности и высокой общности служит для построения моделей сложных объектов и функционирования систем. В теорию входят множество алгоритмов, основными из которых являются поиск в глубину и поиск в ширину. Наличие алгоритмов связывает теорию графов с информатикой и, следовательно, она может изучаться в школе со стороны двух предметов или одного интегрированного.