Графы. Состав графа

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