Элементы теории графов

Цели реферата:
Изучить существующие теории графов.
Научиться применять эти теории при решении логических задач.
Расширить объем нетрадиционных приемов и методов решения логических задач.

Задачи реферата:
Научиться применять некоторые элементы теории графов к решению задач.
Решить несколько задач с помощью теории графов.
Увидеть в теории графов простоту решения и естественность, облегченность в решении казалось бы, не решаемых задач.

Оглавление
I. Введение
II.Основная часть
1.Основные понятия теории графов
2.Эйлеровы графы
3.Плоские графы
4.Мозаика
5. Решение логических задач при
помощи графов.
III.Вывод

Граф
Граф-это конечное множество точек и соединяющих их кривых на плоскости

Эйлеровы графы
Цикл, в котором входящих в неё рёбер столько, сколько и выходящих из неё, то есть вершины графа должны были быть чётными.

Мозаика
С точки зрения теории графов подобная мозаика – это плоский граф. Все грани, которого имеют одно и то же число рёбер и повторяются большое число раз

Плоские графы
Плоский граф – это такой граф, который можно начертить на плоскости так, чтобы его рёбра пересекались только в его вершинах

Пример решения одной из логических задач с чертежами
Задача состоит в следующим. Город Кенигсберг (ныне Калининград) расположен на берегах реки Прегель и двух её островах. Различные части города были соединены семью мостами. По воскресеньям горожане любили прогуливаться по берегам реки, её островам и мостам Вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из какого-то места, вернуться в него, обойдя все мосты в точности по одному разу?

Решение
Для решения этой задачи Эйлер построил граф, с вершинами А,В,С,Д, которого были берега А и В и острова С и Д, а рёбрами соединяющие их мосты. Этот граф изображен на чертеже10.
Задача состоит в том, чтобы на этом графе найти цикл, проходящий по всем его рёбрам в точности по одному разу

Вывод
Изучил некоторые теории графов.
Научился применять эти теории при решении простейших задач.
Расширил объем нетрадиционных приемов и методов решения логических задач