Графы и деревья

или явления.

предметные
информационные
Образные модели
Знаковые модели
Визуализация
различные формы
анимация
Формализация
формальные языки
необходимость моделей и пути построения

Схемы авиалиний
Схемы метро
Иерархия объектов (например структура

школы)
Файлы системы компьютера

рёбер
G – число граней

Кенигсберг. Через город протекает река Преголя, она делится на два

рукава и огибает остров. В 18 веке в городе было семь мостов, расположенных так, как показано на рисунке сверху. Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка? Многие горожане заинтересовались этой задачей. Однако, придумать решение никто не смог. Потом этот вопрос привлек внимание ученых разных стран. Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач.

Решая задачу про Кенигсбергские мосты, Эйлер установил, в частности, следующие три СВОЙСТВА графа:
1) Если все вершины графа четные, то можно одним росчерком (то есть рисуя непрерывно и не проводя дважды по одной и той же линии) начертить граф
2) Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине. Проверьте это свойство на практике.
3) Граф с более, чем двумя нечетными вершинами, невозможно начертить одним росчерком.
В задаче о семи Кенигсбергских мостах все четыре вершины соответствующего графа - нечетные, т.е. нельзя пройти по всем мостам ровно один раз и закончить путь там, где он был начат.

транспортных перевозок. Коммивояжёру, чтобы распродать нужные и не очень нужные

в хозяйстве товары, следует объехать n пунктов и в конце концов вернуться в исходный
пункт. Требуется определить наиболее выгодный маршрут объезда. В качестве меры выгодности маршрута (точнее говоря, невыгодности) может служить суммарное время в пути, суммарная стоимость дороги, или, в простейшем случае, длина маршрута.

Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных

были приглашены 4 врача. Каждый из приглашенных работал в 2

поликлиниках и представлял на этом совещании обе поликлиники. Любая возможная комбинация двух поликлиник имело на этом совещании одного и только одного представителя. Сколько поликлиник в городе? Сколько врачей было приглашено на совещание?

Применение графов для решения логических задач

Ответ: 5 поликлиник;
10 врачей.