Описание предмета: «Теория графов»Теория графов и графовые сети (или просто графы) используются практически во всех областях знаний, в том числе,
в компьютерной науке и практике. В частности, большую часть UML диаграмм можно представить графами. Основное
достоинство графов в том, что их можно рисовать на бумаге или экранах компьютеров в виде точек соединенных
стрелками и/или линиями. Вместе с тем, связанный граф представляется формально с помощью наборов бинарных
отношений и/или множеств, каждое их которых состоит из двух элементов. Графы рисуют на бумаге не только те кто
понимают теорию графов, но и люди, которые никогда о ней не слышали. К примеру, любой администратор,
изображающий структуру, подчиненных ему подразделений в виде прямоугольников и стрелок между ними, по сути
дела, рисует связанный ориентированный граф, хотя он и не знает об этом.
Началом теории графов считается 1736 год, когда вышла в свет статья Эйлера с его знаменитыми рассуждениями о
Кенигсбергских мостах. Затем около 100 лет эта статья оставалась единственной, а методы теории графов
невостребованными практикой. Интерес к графам появился только в середине 19 века благодаря исследованиям
электрических сетей, моделей кристаллов и структур молекул. С тех пор сфера применений теории графов непрерывно
расширялась и сегодня она представляет собой мощную формальную систему, имеющую необозримое множество областей
практического применения.
Теория графов получила широкое развитие с середины 50-х годов 20 века благодаря развитию вычислительной
техники. Граф из-за его наглядности и высокой общности служит для построения моделей сложных объектов и
функционирования систем. В теорию входят множество алгоритмов, основными из которых являются поиск в глубину и
поиск в ширину. Наличие алгоритмов связывает теорию графов с информатикой и, следовательно, она может изучаться
в школе со стороны двух предметов или одного интегрированного.
|
