Анализ графов

1.

2.

Граф – это наглядное средство представления состава и
структуры системы.
Дуга – направленная линия (со стрелкой).
Ребро – ненаправленная (без стрелки).
Петля – линия, выходящая из некоторой вершины и
входящая в неё же.
дуга
В
ребро
вершина
петля
А
С

3.

Применение графов
Часть генеалогического
дерева Л.Н. Толстого.
Вершины – члены рода,
отрезки – отношение
родственности, ведущее
от родителей к детям.

4.

Схема подчинения

5.

Схема метро
Схема железнодорожных
станций

6.

Схема горнолыжных трасс
Географическая карта

7.

Блок-схемы программ для ПК
Начало
Ввод A, B
S=А*B
Вывод S
Конец

8.

Графы в физике и технике
Конструирование печатных схем.

9.

Теория графов в медицине

10.

Задача
С кем Андрей может поделиться секретом, не
рискуя, что он станет известен кому-то другому,
если известно, что
• Андрей дружит с Дашей,
• Андрей с Машей,
• Даша с Колей,
Андрей
Даша
• Коля с Андреем.
Маша
Коля

11.

Задача
Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече
обменялись рукопожатиями (каждый пожал руку каждому
по одному разу).
Сколько всего рукопожатий было сделано?

12.

Задача 2. В таблице приведена стоимость
перевозок между соседними
железнодорожными станциями.
Укажите схему, соответствующую таблице.

13.

Задача 3. Между населёнными пунктами A, B, C, D, E, F
построены дороги, протяжённость которых приведена в
таблице. Определите длину кратчайшего маршрута из А в F.
А
A
B
2
C
4
B
C
2
4
1
1
D
E
D
3
F
1. A-B-C-D-E-F
(2+1+3+3+2=11)
4
B
2
F
А
1
4
C
7
3
7
E
4
7
3
3
4
F
2
2
2
2. A-B-C-E-F
(2+1+4+2=9)
3
E
3. A-B-E-F
(2+7+2=11)
Ответ: 9
3
D
4. A-C-D-E-F
5. A-C-E-F
(4+3+3+2=12) (4+4+2=10)

14.

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