Информационные модели на графах Наглядным средством представления и структуры системы является граф. - презентация

1 Информационные модели на графах Наглядным средством представления и структуры системы является граф

2 Граф состоит из вершин, связанных линиями. Если линия направленная ( со стрелками), то она называется дугой Линия ненаправленная (без стрелок) называется ребром. Линия, выходящая из вершины и входящая в нее же, называется петлей.

3 Графы - схемы отношений, отражающие связи между объектами. Например, граф, отражающий отношение «переписываются» между объектами класса «дети» может выглядеть, как показано на рис.

4 Отношение «переписываются» является двухсторонним (симметричным). Поэтому соответствующие вершины соединены линиями без стрелок (ребрами). Граф называется неориентированным, если его вершины соединены ребрами.

5 Путь по вершинам и ребрам графа, включающий любое ребро графа не более одного раза, называется цепью. Пример цепи: Юра - Аня - Витя - Коля.

6 Цепь, начальная и конечная вершины которой совпадают, называется циклом. Пример цикла: Аня - Коля - Витя - Аня.

7 Иначе выглядит граф, отражающий отношение «пишeт письма» между теми же объектами класса «дети». Линии со стрелками (дуги) придают ему совершенно иной смысл Юра Аня Витя Коля Маша

8 Граф называется ориентированным, если его вершины соединены дугами Граф называется взвешенным, если его вершины или ребра (дуги) характеризуются величиной – весом вершины или ребра (дуги)

9 Информация о городах Золотого кольца вес вершин – год основания, вес ребер – расстояние между городами

10 Сказка про Царевну-лягушку представлена в виде графа стрела Кощей Бессмертный прилетела превратилась

11 ГИА 9 класс Задание 4

12

13

14

15 Грунтовая дорога проходит последовательно через населенные пункты А, В, С и D. При этом длина дороги между Аи В равна 80 км, между В и С – 50 км, между С и D – 10 км. Между А и С построили новую асфальтовую дорогу длиной 40 км. Оцените минимальное возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/ч, а по асфальту – 40 км/ч? 1 час2)1,5 часа3) 3,5 часа 4) 4 часа A B C D Решение: АВ=80:20 =4 ч АС+СВ=40:40+50:20= =1+2,5=3,5 ч Ответ:3

16 Стоимость перевозок между станциями указана в таблице. Есть ли путь от А до D, где стоимость перевозок меньше 6? АВСDЕ А141 В1 С432 D3 Е12