Моделирование на графах

Моделирование на графах

Оформляют таблицы в соответствии с ГОСТ 2.105-95 «ЕСКД»

Таблицы могут быть следующими типами:

«Объект — свойство», содержащими информацию о свойствах отдельных объектов, принадлежащих одному классу.

«Объект — объект», содержащими информацию о некотором одном свойстве пар объектов, принадлежащих одному или разным классам.

Давайте рассмотрим, пожалуй, самую известную головоломку, придуманную в XVIII веке, и захватившую умы человечества на многие годы. Называется она задача о семи Кёнигсбергских мостах.
В Кёнигсберге, начиная с XIV было построено 7 мостов: Медовый мост, Лавочный мост, Зелёный мост, Рабочий мост, Кузнечный мост, Деревянный мост и Высокий мост, соединяющий остров и полуострова в единый город.
Тогда и возникла головоломка: «Как пройти по всем мостам, не проходя ни по одному дважды?»

Десятилетиям жители города пытались решить эту задачу как практически (гуляя по городу), так и теоретически.
И только Леонард Эйлер, введя новое понятие — ГРАФ, смог решить ее раз и навсегда.

является многосвязной структурой,
обладающей свойствами:
— на каждый элемент может быть произвольное количество ссылок;
— каждый элемент может иметь связь с любым количеством элементов;
— каждая связка может иметь направление и вес.
Направленная (без стрелки) линия, соединяющая вершины графа, называется ребром.
Линия направленная (со стрелкой) называется дугой.

Граф называется неориентированным, если его вершины соединены ребрами.

Граф называется ориентированным, если его вершины соединены дугами.

Граф называется взвешенным, если его вершины или ребра характеризуются некоторой дополнительной информацией — весами вершин или ребер. (когда у вершины или у ребра есть вес, отличающий его от другого)

1. Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно или не может существовать граф, который имел бы нечётное число нечётных вершин.
2. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
3. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
ВЫВОД: пройти только один раз по каждому мосту невозможно.

С помощью графов можно планировать оптимальные транспортные маршруты, упростить решение математических задач, визуализировать решения компьютерных программ, визуализировать различную информацию (схема метро, карта звездного неба и т. д.).

Очень часто для решения задач требуется найти кратчайший путь между двумя вершинами.
Кратчайшим путем будем называть путь, если: эти вершины соединены минимальным числом ребер (в случае, если граф невзвешенный); сумма ребер, соединяющих эти вершины, минимальна (для взвешенного графа).

Существует огромное количество алгоритмов, находящих кратчайший путь и один из них — это алгоритм Дейсктры.
 
Алгоритм заключается в том, что надо пошагово перебрать все вершины графа, вычеркивая их, которые будут являются известным минимальным расстоянием от вершины «начала» до конкретной вершины.

Для примера возьмем взвешенный ориентированный граф и попытаемся найти кратчайший путь от вершины A до F.
Пошагово переберём все вершины графа, которые будут являются известным минимальным расстоянием от вершины «начала» до конкретной вершины.
Присвоим вершине А метку равную 0, потому как эта вершина — начало. Остальным вершинам присвоим метки равные бесконечности.

То есть :

B=0+2=2
C=0+5=5
D=0+7=7
F=0+10=10

Еще одним способом нахождения кратчайшего пути может служить метод динамического программирования.

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