Связность графа

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3

ГЛАВА 1. ИЗУЧЕНИЕ ПОНЯТИЯ «ГРАФ» 5

1.1 Простой граф 5

1.2 Общий граф 6

1.3 Орграф 7

ГЛАВА 2. ИЗУЧЕНИЕ ПОНЯТИЯ «СВЯЗНОСТЬ ГРАФОВ» 9

2. 1 Общие положения 9

2.2 Теорема о несвязности графов 10

Ниже представлено следствие из теоремы о несвязности графов. 11

2.3 Свойства графов 11

ЗАКЛЮЧЕНИЕ 13

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 16

ВВЕДЕНИЕ

Л. Эйлер - швейцарский российский и немецкий математик, который внес огромный вклад в развитие теории графов. Первые упоминания, которые можно отнести к теории графов, были найдены в письмах математика. Например, в письме датируемом 1736 годом Леонард Эйлер сформулировал задачу про семь кёнигсбергских мостов. Помимо формулировки этой задачи он предложил ее решение.

Задача о кёнигсбергских мостах заключается в следующем, необходимо посетить все семь мостов только один раз (рисунок 1).

Рисунок 1 – Семь мостов Кёнигсберга

Решение данной задачи, предложенное Л. Эйлером, послужило образованию эйлеровских циклов. Данная задача является классической задачей теории графов.

Теорией графов принято называть область дискретной математики, которая изучает свойства графов.

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

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

В виду всего вышесказанного доказывается актуальность рассматриваемой темы в настоящей курсовой работе.

Целью данной работы является изучение понятия «связность графа».

Поставленная цель потребовала постановки следующих задач:

1. Изучение понятия «граф»;

2. Изучение понятия «связность графа».