Similar presentations:
Анализ графов
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 путей