Похожие презентации:
Графы. Состав графа
1. ГРАФЫ
Л.Л. Босова, УМК по информатике для 5-7 классовГРАФЫ
Москва, 2007
1 из 15
2. Состав графа
Граф состоит из вершин, связанных линиями.Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется
ребром.
Линия, выходящая из некоторой вершины и входящая
в неё же, называется петлей.
дуга
А
ребро
В
петля
С
2 из 15
3. Неориентированный граф -
Неориентированный граф граф, вершины которого соединены ребрами. Спомощью таких графов могут быть представлены
схемы двухсторонних (симметричных) отношений.
Юра
Аня
Маша
Коля
Витя
Граф, отражающий отношение «переписываются»
между объектами класса «дети»
3 из 15
4. Граф отношения «переписываются»
Цепь – путь по вершинам и ребрам, включающийлюбое ребро графа не более одного раза.
Цикл – цепь, начальная и конечная вершины которой
совпадают. Граф с циклом называют сетью.
Юра
Аня
Маша
Коля
Витя
Приведите примеры цепи и цикла.
4 из 15
5. Ориентированный граф -
граф, вершины которого соединены дугами. Спомощью таких графов могут быть представлены
схемы односторонних отношений.
Юра
Аня
Маша
Коля
Витя
Граф, отражающий отношение «пишет письма».
Приведите примеры цепи и цикла.
5 из 15
6. граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).
Взвешенный граф граф, у которого вершины или рёбра (дуги) несутдополнительную информацию (вес).
182
127
158
Москва, 1147
Владимир, 1108
Переславль Залесский, 1152
Каким весом характеризуются вершины и дуги данного графа?
6 из 15
7. Семантическая сеть
указалапустил
Иван-Царевич
нашел
Стрела
Баба Яга
сжег
Лягушачья кожа
прилетела
Лягушка
победил
сбросила
нашел
превратилась
Василиса Прекрасная
Лебедь
превратилась
улетела
Кощей Бессмертный
7 из 15
8. Иерархия -
это расположение частей или элементов целого впорядке от высшего к низшему.
Директор
Заместители директора
Учителя
Ученики
8 из 15
9. Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов
и петель.компьютер
суперкомпьютер
настольный
рабочая станция
персональный
компьютер
портативный
карманный
Классификация компьютеров
9 из 15
10.
Корень – главная вершина дерева.Предок – объект верхнего уровня.
Потомок – объект нижнего уровня.
Листья – вершины, не имеющие потомков.
Укажите перечисленные объекты у дерева
Чемпион
Финалисты
Участники ½ финала
Участники ¼ финала
Первоначальные игроки
Олимпийская система спортивных соревнований
10 из 15
11. Файловая структура
Укажите корневую вершину, объекты 1-го, 2-го и 3-го уровней11 из 15
12.
Давайте обсудим1. Какая связь между графом и таблицей на
рисунке?
12 из 15
13.
В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными буквами A, B, C, D и E. Укажите схему, соответствующую таблице.В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными буквами A, B, C, D и E. Укажите схему, соответствующую таблице
В таблице приведена стоимость перевозок между пятью
железнодорожными станциями, обозначенными буквами A, B,
C, D и E. Нарисуйте граф, соответствующий таблице.
A
A
B
C
D
E
B
C
1
4
1
4
D
E
1
3
2
3
1
2
13 из 15
14.
A—B—C—D—E: длина маршрута 13 км.A—B—D—E: длина маршрута 10 км.
A—C—D—E: длина маршрута 10 км.
A—C—B—D—E: длина маршрута 9 км.
Между населёнными пунктами А, В, С, D, Е
построены дороги, протяжённость которых (в
километрах) приведена в таблице:
Определите длину
A—B—C—D—E: длина
маршрута пути
13 км.
кратчайшего
между
пунктами 10
А икм.
E.
A—B—D—E: длина маршрута
Передвигаться можно
A—C—D—E: длина маршрута
км.
только по10
дорогам,
протяжённость которых
A—C—B—D—E: длина
маршрута
9 км.
указана
в таблице.
A
5
3
B
D 1
4
E
1
6
C
14 из 15
15.
На схеме отражено наличие дорог между пятью городами: A, B,C, D и E. Укажите таблицу, соответствующую схеме (единица
на пересечении строки и столбца указывает на наличие дороги
между городами).
A B C D E
A B C D E
A
1
1
A
1
B 1
1
B 1
1
C
C
1
D 1 1
D 1
1
E
E
1
1
1 1
1
1
1
1
A B C D E
A
1
B 1
1
1
1
A B C
A
1
B
1
1
1
1
C
D 1
1
1
D 1
1
E
1
E
1
1
1
1
C
1
D E
1
1
1
1
1
15 из 15
16.
В таблице приведена стоимость перевозок междупятью железнодорожными
станциями, обозначенными
буквами A, B, C, D и E. Укажите схему, соответствующую
таблице.
16 из 15
17.
На рисунке — схемадорог, связывающих
города А, Б, В, Г, Д, Е, Ж
и К. По каждой дороге
можно двигаться только
в одном направлении,
указанном стрелкой.
Сколько существует
различных путей из
города А в город К?
NК = N Е + NВ + N Г + NЖ
Аналогично:
NЕ = NБ + NВ = 1 + 1 = 2;
NЖ = NД = 1;
NВ = NА = 1;
NГ = NВ + NА + NД = 1 + 1 + 1 = 3;
NД = NА = 1;
NБ = NА = 1.
Подставим найденные значения: N = 2 + 1 + 3 + 1 = 7.
17 из 15