close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Информационные модели
на графах
Наглядным средством
представления и структуры
системы является граф
• Граф состоит из вершин,
связанных линиями.
• Если линия направленная ( со
стрелками), то она называется
дугой
• Линия ненаправленная (без
стрелок) называется ребром.
• Линия, выходящая из вершины и
входящая в нее же, называется
петлей.
• Графы - схемы отношений,
отражающие связи между объектами.
• Например, граф, отражающий
отношение «переписываются» между
объектами класса «дети» может
выглядеть, как показано на рис.
Отношение «переписываются»
является двухсторонним
(симметричным). Поэтому
соответствующие вершины соединены
линиями без стрелок (ребрами). Граф
называется неориентированным,
если его вершины соединены ребрами.
Путь по вершинам и ребрам графа,
включающий любое ребро графа не
более одного раза, называется цепью.
Пример цепи: Юра - Аня - Витя - Коля.
Цепь, начальная и конечная вершины
которой совпадают, называется
циклом.
Пример цикла: Аня - Коля - Витя - Аня.
Иначе выглядит граф, отражающий
отношение «пишeт письма» между
теми же объектами класса «дети».
Линии со стрелками (дуги) придают
ему совершенно иной смысл
Юра
Аня
Витя
Маша
Коля
Граф называется ориентированным,
если его вершины соединены дугами
Граф называется взвешенным, если его
вершины или ребра (дуги)
характеризуются величиной – весом
вершины или ребра (дуги)
Информация о городах Золотого кольца
вес вершин – год основания, вес ребер –
расстояние между городами
Сказка про Царевну-лягушку
представлена в виде графа
стрела
прилетела
превратилась
Кощей Бессмертный
ГИА 9 класс
Задание 4
Грунтовая дорога проходит последовательно через
населенные пункты А, В, С и D. При этом длина
дороги между Аи В равна 80 км, между В и С – 50 км,
между С и D – 10 км. Между А и С построили новую
асфальтовую дорогу длиной 40 км. Оцените
минимальное возможное время движения
велосипедиста из пункта А в пункт В, если его
скорость по грунтовой дороге – 20 км/ч, а по
асфальту – 40 км/ч?
1 час 2)1,5 часа 3) 3,5 часа 4) 4 часа
A
80
B
40
50
Решение:
АВ=80:20 =4 ч
АС+СВ=40:40+50:20=
=1+2,5=3,5 ч
Ответ:3
C
D
10
Стоимость перевозок между станциями
указана в таблице. Есть ли путь от А до
D, где стоимость перевозок меньше 6?
А
А
В
1
С
4
D
Е
В
С
1
4
2
Е
1
3
3
1
D
2
1/--страниц
Пожаловаться на содержимое документа