Структура информации: графы и деревья

1. Структура информации

§ 1. Структура информации
§ 2. Графы. Матрица смежности
§ 3. Связные графы
§ 4. Взвешенные графы. Весовая матрица
§ 5. Кратчайший путь в графе
§ 6. Ориентированные графы
§ 7. Задача нахождения количества путей

2. Структура информации

§ 1. Структура информации

3. Примеры

3
Примеры
Вариант 1
«Для того, чтобы добраться до села Васино, нужно
сначала долететь на самолете до Ивановска.
Затем на электричке доехать до Ореховска. Там
на пароме переправиться через реку Слоновую в
поселок Ольховка, и оттуда ехать в Васино на
попутной машине».
Вариант 2
Как ехать в Васино?
1) На самолете до Ивановска.
2) На электричке до Ореховска.
3) На пароме через р. Слоновую в пос. Ольховка.
4) На попутной машине до с. Васино.

4. Примеры

4
Примеры
Вариант 3
Откуда
Москва
Ивановск
Ореховск
пос. Ольховка
Куда
Ивановск
Ореховск
пос. Ольховка
с. Васино
Транспорт
самолет
электричка
паром (р. Слоновая)
попутная машина
Вариант 4
Москва
Ивановск
самолёт
Ореховск
электричка
Ольховка
паром
р. Слоновая
Васино
попутная
машина
? Какой вариант лучше? Почему?

5. Структурирование

5
Структурирование
Структурирование — это выделение важных
элементов в информационных сообщениях и
установление связей между ними.
Цель — облегчение восприятия и поиска
информации.
Оглавление:
1. Информация
1.1 Что такое информация?
1.2 Виды информации
1.3 Информация в природе
1.4 Информация в технике
2. Измерение информации
2.1 Что такое бит?
2.2 Байт и другие единицы
5
6
8
10
11
12
13
14
Словарь:
Индекс:
автомат – automaton
автор – author
адрес – address
алгебра – algebra
алгоритм – algorithm
архив – archive
архитектура – architecture
асимметрия – asymmetry
А
аксиома 45
алгоритм 30, 78
архиватор 125
Б
бит 5, 15, 25, 43
брандмауэр 112
браузер 322

6. Множество

6
Множество
• перечисление элементов
– Вася, Петя, Коля
– 1, 17, 22, 55
• по характерному признаку
– множество натуральных чисел
– множество драконов с тремя хвостами
!
Порядок перечисления не важен!
• процессор
• память
• устройства ввода
• устройства вывода
маркированный
список

7. Линейный список

7
Линейный список
Москва
!
Ивановск
Ореховск
Ольховка
Васино
Порядок следования элементов важен!
1) надеть носки
2) надеть ботинки
3) выйти из дома
нумерованный
список

8. Таблица

8
Таблица
свойства
Фамилия
Иванов
Петров
Сидоров
Имя
Иван
Петр
Сидор
Рост, см
175
164
168
Год рождения
1996
1998
2000
объект
свойства
Марка
Мощность двигателя, л.с.
Максимальная скорость, км/ч
Время разгона до 100 км/ч, с
Вес, кг
67
70
63
Лада Приора
98
183
11,5
Лада Калина
89
165
12,5
ВАЗ 2110
79
165
14
объект
ВАЗ 21099
70
156
15

9. Иерархия (дерево)

9
Иерархия (дерево)
директор
Уровень 1
главный инженер
Уровень 2
Уровень 3
Петров
Иванов
лист
главный бухгалтер
Фомин
лист
лист
Алексеева
лист
лист
дуга
узел
корень
Сидорова

10. Деревья

10
Деревья
A
B
D
C
E
«Сыновья» А: B, C.
F
G
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G. «Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).

11. Деревья – классификации

11
Деревья – классификации
Хищные
Псообразные
Псовые
Енотовые Медвежьи
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые
…
Кошкообразные
Кошачьи
Гиеновые Мангустовые
многоуровневый
список

12. Иерархия – файловая система

12
Иерархия – файловая система
Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Папа.jpg
Мама.gif
Папа.jpg
Мама.gif
Документы
Тексты
Доходы.doc
Расходы.odt
Фотографии
Отдых.txt
Папа.jpg
Мама.gif

13. Структура информации

§ 2. Графы. Матрица
смежности графа

14. Графы

14
Графы
«От посёлка Васюки три дороги идут в
посёлки Солнцево, Грибное и Ягодное.
Между Солнцевым и Грибным и между
Грибным и Ягодным также есть дороги.
Кроме того, есть дорога, которая идет
из Грибного в лес и возвращается
обратно в Грибное».
?
Как структурировать?

15. Графы

15
Графы
Солнцево
A
C
B
D
Грибное
Васюки
!
Ягодное
Граф – это набор вершин и связей
между ними (рёбер).

16. Матрица и список смежности

16
Матрица и список смежности
Матрица смежности
A
B
C
D
A
B
C
D
Список смежности
(
A (B, C),
B (A, C, D),
C (A, B, С, D),
D (B, C) )
A
0
1
1
0
B
1
0
1
1
C
1
1
1
1
D
0
1
1
0
петля

17. Постройте матрицу смежности

17
Постройте матрицу смежности
A
A
A
A
B
C
D
D
C
B
B
C
B
D
C
A
A
B
C
D
D
B
C
D

18. Постройте матрицу смежности

18
Постройте матрицу смежности
A
A
D
D
B
C
B
A
A
B
C
D
B
C
C
D
A
A
B
C
D
B
C
D

19. Нарисуйте граф

19
Нарисуйте граф
A
A
B
C
D
0
1
1
B
0
1
0
C
1
1
0
D
1
0
0
A
A
B
C
D
1
0
1
B
1
1
0
C
0
1
1
D
1
0
1

20. Нарисуйте граф

20
Нарисуйте граф
A
B
C
D
E
A B
0
0
1 1
1 0
0 1
C D E
1 1 0
1 0 1
0 1
0
0
1 0
A
B
C
D
E
A B
0
0
1 1
1 0
1 0
C D E
1 1 1
1 0 0
0 1
0
0
1 0

21. Нарисуйте граф

21
Нарисуйте граф
A
B
C
D
E
A B
0
0
1 1
1 0
1 1
C D E
1 1 1
1 0 1
0 1
0
0
1 0
A
B
C
D
E
A B
0
0
0 1
1 0
0 1
C D E
0 1 0
1 0 1
1 1
1
0
1 0

22. Структура информации

§ 3. Связные графы

23. Связность графа

23
Связность графа
A
C
B
D
!
Связный граф – это
граф, между любыми
вершинами которого
существует путь.
Солнцево
A
C
B
D
Грибное
Васюки
Ягодное
компоненты связности

24. Дерево – это граф?

24
Дерево – это граф?
!
Дерево – это связный граф без
циклов (замкнутых путей).
A
A
C
B
D
B
ABC
BCD
D
ABDC
CCC…
H
C
E
F
G
J
дерево

25. Структура информации

§ 4. Взвешенные графы.
Весовая матрица
© К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

26. Взвешенные графы

26
Взвешенные графы
2
Солнцево
12
8
A
Грибное
5
B
Ягодное
Васюки
2
C
5
12
4
8
6
4
D
6
вес ребра
Весовая матрица:
A
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4

27. Постройте весовую матрицу

27
Постройте весовую матрицу
A
1
B
A
B
C
D
A
4
3
1
C
A
B
3
2
C
D
D
1
2
B
C
4
A
A
B
C
D
B
D
C
D

28. Постройте весовую матрицу

28
Постройте весовую матрицу
2
A
1
B
A
A
B
C
D
3
D
1
4
B
1
D
A
A
B
C
D
2
1
B
C
C
A
D
C
4
B
C
D

29. Нарисуйте граф

29
Нарисуйте граф
A
A
B
C
D
B
4
C
3
4
3
D
2
6
2
6
A
B
C
D
A
B
C
2
2
3
4
5
D
3
4
5

30. Нарисуйте граф

30
Нарисуйте граф
A
B
C
D
E
A B
4
4
3
2
7
C D E
3
7
2
6
6
1
1
A
B
C
D
E
A B
2
2
5
3
6
C D E
5
6
3
1
1

31. Нарисуйте граф

31
Нарисуйте граф
A B
A
B
C 2
D 2
E 6
2
C D E
2 2 6
2
2
2
A
B
C
D
E
A B
5
5
2
5
6
C D E
2
6
5
2
2
3
3

32. Структура информации

§ 5. Кратчайший путь в графе

33. Кратчайший путь (перебор)

33
Кратчайший путь (перебор)
A B
2
A
B 2
C 4 1
D
E 6
C D E
4
6
1
5 1
5
3
1 3
Определите кратчайший путь
между пунктами A и D.
2
B
A
4
С
2
6
E
4
1
С
5
D
8
1
С
3
1
E
4
3
дерево возможных
путей
D
7
6
3
7
D
9

34. Кратчайший путь

34
Кратчайший путь
A B
2
A
B 2
C 4 1
D
7
E
C D E
4
1
7
3 5
3
3
5 3
Определите кратчайший
путь между пунктами A и E.

35. Кратчайший путь

35
Кратчайший путь
A B
A
B
C 3
D 1
E
4
C D E
3 1
4
2
2
2
2
Определите кратчайший
путь между пунктами A и B.

36. Кратчайший путь

36
Кратчайший путь
A B
A
B
C 3
D 1
E 1
4
C D E
3 1 1
4
2
2
Определите кратчайший
путь между пунктами A и B.

37. Кратчайший путь

37
Кратчайший путь
A B
A
B
C 3
D 1
E 4
4
C D E
3 1 4
4
2
2
2
2
Определите кратчайший
путь между пунктами A и B.

38. Кратчайший путь

38
Кратчайший путь
A B
A
B
C
D 1
E
4
1
C D E
1
4
1
4 2
4
2
Определите кратчайший
путь между пунктами A и B.

39. Структура информации

§ 6. Ориентированные графы

40. Ориентированные графы (орграфы)

40
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец),
рёбра называю дугами.
Солнцево
12
8
Грибное
5
Ягодное
6
!
A
Весовая матрица
может быть
несимметрична!
B
A
A
B
C
D
12
C
5
12
4
Васюки
8
4
D
6
B
12
C
8
5
4
D
6
4

41. Нарисуйте орграф

41
Нарисуйте орграф
A B
A
B 2
C 3
D 1
E
C D E
3 1
4
2
2
A B
A
B
C 3
D
E
4
2
C D E
5 1
6 4
3
3

42. Нарисуйте орграф

42
Нарисуйте орграф
A B
A
B
C
D
E 4
4
C D E
3 1 4
4
2
2
2
A B
A
B
C 3
D 1
E 1
4
2
1
C D E
1
4
1
4 2
4
2

43. Структура информации

§ 7. Задача нахождения
количества путей в
ориентированном графе.

44. Количество путей из А в Ж

44
Количество путей из А в Ж
Б
1
1
Д
1+1+1=3
1
А
Ж
Г
В
!
1
1+1+1+1+3=7
Е 1
NЖ= NД + NБ + NГ + NВ + NЕ

45. Количество путей из А в К

45
Количество путей из А в К
Д
Б
B
Е
А
Г
З
Ж
К
И

46. Количество путей из А в К

46
Количество путей из А в К
Д
Б
B
Е
А
Г
З
Ж
К
И

47. Количество путей из А в К

47
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
З
И

48. Количество путей из А в К

48
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
З
И

49. Количество путей из А в Л не через В

49
Количество путей из А в Л не через В
Сколько существует различных путей из
города А в город Л, не проходящих через B?
Д
Б
Ж
В
А
Г
И
Е
Л
К

50. Количество путей из А в Л через Д

50
Количество путей из А в Л через Д
Сколько существует различных путей из
города А в город Л, проходящих через Д?
Д
Б
Ж
В
А
Г
И
Е
Л
К

51. Количество путей из А в Л через Д

51
Количество путей из А в Л через Д
Сколько существует различных путей из
города А в город Л, проходящих через Д?
Д
Б
В
А
Г
И
Ж
Е
Л
К