Графы. Graafid.. Граф – обобщённая иерархическая структура. Граф состоит из: - множества элементов данных (вершин), - множества рёбер. Graaf on andmestruktuur, - презентация

1 Графы. Graafid.

2 Граф – обобщённая иерархическая структура. Граф состоит из: - множества элементов данных (вершин), - множества рёбер. Graaf on andmestruktuur, mis koosneb tippude hulgast ja servade hulgast. Serv on tippude hulga kahest elemendist koosnev paar. Солт-Лэйк-Сити Сан-Франциско Сан-Диего Феникс Альбукерк

3 4 Tipp Вершина 1 Serv Ребро Кujutatud graafi tipud on 1 kuni 6 ja servad 12, 13, 14, 23, 25 ja 36.

4 Направленный граф Ненаправленный граф DIRECTED GRAPH UNDIRECTED GRAPH Orienteeritud Orienteerimata А B C E D А B C E D Путь: {A,C}, {A,D}, {B,A}, {E,B} {A,B}, {B,A}, {A,C}, {C,A}, {A,D}, {D,E}, {B,D} {D,A}, {B,D}, {D,B}, {B,E},{E,B}

5 Матрица смежности: Maatriksesitus A B C D E A B C D E A B C D E A B C D E Представление графов. Graafi esitamine AB C E D Взвешенный граф Kaalutud graaf Невзвешенный граф Mittekaalutud graaf AB D C E Единицей обозначается наличие ребра между вершинами графа.

6 Если граф задан списком рёбер, то это означает, что в файле содержится некоторое количество строк, в каждой из которых располагается пара чисел i, j, обозначающих вершины, соединённые данным ребром. #include void main() { int **Graf, i, j, N; ifstream input (Graf.txt);//открывает файл для чтения input>>N; //читает из файла количество вершин в графе //выделяет динамическую память для матрицы смежности графа Graf = new int *[N]; for (i=0; i>j; Graf[i][j]=1; Graf[j][i]=1; } return 0; }

7 Списковое представление. Naabrite esitus nimistuses. Вершины Список смежных вершин Tipud Naabri tippude nimistu AB2C1 BC4 CB5 DC7 EB3 AB C E D Взвешенный граф BAC CA DE EC ABCD Невзвешенный граф AB D C E

8 Программа, представляющая граф в виде списка смежности #include void main() { int **Graf, i, j, pos, N; ifstream input (Graf.txt); //открывает файл для чтения input>>N; //читает из файла количество вершин в графе //выделяет динамическую память для матрицы смежности графа Graf = new int *[N]; for (i=0; i>j; Graf[0][pos]=i; Graf[1][pos]=j; pos++; } return 0; }

9 Строковое представление Stringesitus Võetud on graafi maatriksesitus ja selle read üksteise järele kirjutatud. Kuna stringi mahub 256 baiti, saab nii esitada kuni 16-tipulisi graafe. Kui minna bitt-töötlusele (igale tipupaarile mitte 1 bait, vaid 1 bitt), saab nii mahutada kuni 45-tipulisi graafe. Невзвешенный граф AB D C E

10 Управление светофорами на перекрёстке дорог. Сложный перекрёсток Teerist D E C B A Дороги (teed) С и Е – односторонние (ühesuunaline liiklus), остальные (teised) – двухсторонние (kahepoolsed). Всего на этом перекрёстке возможны 13 поворотов. Riistil on 13 pööramist. Некоторые из этих поворотов, такие как АВ (поворот с дороги А на дорогу В) и ЕС, могут выполняться одновременно. Mõned pööramised võivad täida sünkroonsed. Трассы других поворотов, например, AD и ЕВ, пересекаются, поэтому их нельзя выполнять одновременно.

11 Необходимо создать программу, в которой - входные данные – это множество всех допустимых поворотов на перекрёстке (продолжение прямой дороги, проходящей через перекрёсток, также будем считать поворотом) -множество разбиваем так, чтобы все повороты в группе могли выполняться одновременно, не создавая проблем друг для друга. Затем необходимо сопоставить с каждой группой поворотов соответствующий режим работы светофоров на перекрёстке. При этом желательно минимизировать число разбиений исходного множества поворотов, т.к. при этом минимизируется количество режимов работы светофоров на перекрёстке.

12 Для построения модели этой задачи можно применить математическую структуру, известную как граф. Для решения задачи управления движением по перeкрёстку можно нарисовать граф, где вершины будут представлять повороты, а рёбра соединят ту часть вершин-поворотов, которые нельзя выполнить одновременно. Для нашего перекрёстка соответствующий граф может выглядеть так: AB AC BA DA EA BC AD BD DC EC ED EB DB

13 ABACADBABCBDDADBDCEAEBECED AB1111 AC11111 AD111 BA BC111 BD11111 DA11111 DB111 DC EA111 EB11111 EC1111 ED ТАБЛИЦА НЕСОВМЕСТИМЫХ ПОВОРОТОВ На пересечении строки i и столбца j стоит «1» толькo в том случае, если существует ребро между этими вешинами i, j.

14 Задание. Ülesanne. Составить программу на основе матрицы смежности для определения кратчайшего пути от одной вершины до другой. Koostada programmi maatriksesituse abil, mis arvutab kõige lühidam tee tipust tipuni.