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

1

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

3 55 ** --**

4 Вершина графа Ребро графа (без стрелки), весь граф называется неориентированным Дуга графа (со стрелкой), весь граф называется ориентированным A B C D E F Вес дуги или ребра, весь граф называется взвешенным Петля 5

5 План помещения, где будет проходить выставка. Закрашенные места это подсобные помещения, незакрашенные территория выставки. ХВОСТ БАРБОСА Собаки с рыжими хвостами Себе овсянку варят сами. Тем, чьи хвосты стального цвета, Не позволяют делать это. Кто варит сам себе овсянку, Гулять выходит спозаранку. Все, кто гулять выходят рано, Не терпят фальши и обмана. Вид добродушный у Барбоса, Но на сорок он смотрит косо. Он видит: норовят сороки У воробьёв списать уроки! Скажите – проще нет вопроса! – Какого цвета хвост Барбоса?

6 К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города. Этиловый спирт: C2H5 OH Квадратный трехчлен: ax 2 +bx+c

7 Задача: Путешественник пришел в 08:00 на автостанцию населенного пункта ЛИСЬЕ и обнаружил следующее расписание автобусов для всей районной сети маршрутов: Определите самое раннее время, когда путешественник сможет оказаться в пункте ЗАЙЦЕВО согласно этому расписанию. 1) 09:05 2) 12:15 3) 12:25 4) 13:25

8 Строки и столбцы соответствуют вершинам графа (матрица обязательно квадратная) Элемент матрицы = 0, если соответствующие вершины не связаны. Элемент матрицы = 1, если соответствующие вершины связаны, но дуга или ребро не имеют веса (граф не взвешенный). Элемент матрицы = весу ребра (дуги), если соответствующие вершины связаны и граф взвешенный.

9 А А А B B B C C C D D E E ABC A010 B101 C010 ABCDE A01000 B00110 C00000 D00000 E00010 ABCDE A B C D E

10 1. Представить в виде графа расписание электричек для станции Челябинск- главная: 2. Составить граф по матрице смежности: НомерПоездПрибытиеОтправ ление 6801Челябинск - Троицк 02: Кисегач- Челябинск 05: Каясан- Челябинск 19: Челябинск- Еманжелинск 18: Шумиха- Челябинск 21:27 АБВГДЕЖ А Б В Г Д Е Ж

11 3. Составить матрицу смежности для ориентированного графа: 4. Составить матрицу смежности для взвешенного графа: 5. Представить граф в виде выражения: 6. Представить выражение в виде графа: (2a+7ab)(5a-6b) A G C E D B F a + 72bba * * - / A B C D E F

12 Задача: найти длину кратчайших путей из заданной вершины во все остальные вершины взвешенного графа. Алгоритм Дейкстры: 1.Для каждой вершины задаем начальное значение путей: для начальной = 0, для остальных =. 2.Из непройденных выбираем вершину с наименьшим путем. Помечаем ее как пройденную. 3.Для всех исходящих из текущей вершины ребер: путь соседней вершины = меньшее из пути этой соседней вершины и пути текущей + вес ребра между ними. 4.Если есть непройденные вершины, возврат к п A B C D E ABCDE

13 E K L F D C B A G

14 Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 92) 103) 114) 12 ABCDEF A B C D E F000020

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

16 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? 1. А Б Д И К 2. А Б Д К 3. А Б В Д И К 4. А Б В Д К 5. А Б В Ж К 6. А В Д И К 7. А В Д К 8. А В Ж К 9. А Г В Д И К 10. А Г В Д К 11. А Г В Ж К 12. А Г Е Ж К 13. А Г Е К