Основы теории графов

Краткое описание

Содержание

Введение...3

1.Понятие графов…4

2.Основы построения графов. Виды графов…15

  2.1.Ориентированные графы…15

  2.2.Степень вершины…17

  2.3.Циклы и пути в графе…19

  2.4.Связность графа…20

  2.5.Виды графов…21

  2.6.Деревья, лес…31

  2.7.Матрицы графов…33

Список использованной литературы…6

Введение

Теория графов – обширный самостоятельный раздел дискретной математики.

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

Годом рождения теории можно считать 1736 г. Л.Эйлер решил задачу о кенигсбергских мостах, которая привела к нахождению критерия существования в графе специального маршрута. Термин «граф» был предложен в 1936 г. венгерским математиком Д.Кенигом.

Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

Для работы с графами в Maple V предназначена библиотека networks. Команда подключения этой библиотеки стандартная, т.е. достаточно воспользоваться оператором with. Граф в Maple представляется особой процедурой типа GRAPH. Для работы с графами можно воспользоваться любой из 75-ти функций, содержащихся в библиотеке networks. 

Целью курсовой работы является рассмотрение основ теории графов.