Графические информационные модели

МНОГООБРАЗИЕ ГРАФИЧЕСКИХ ИНФОРМАЦИОННЫХ МОДЕЛЕЙ
Схема
Карта
Чертёж
Диаграмма
Графическая
модель
График
Граф

Схемы в физике

Схемы в истории

Схемы в биологии
Р
♀
♂
х
АА
генотип
аа
гаметы
F1
Аа
х

Схемы в информатике

Географическая карта Евразии

Чертёж детали

График описания движения

Диаграмма

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

Граф – это набор вершин (узлов) и связей между ними (рёбер).
ГРАФЫ

МАТРИЦА И СПИСОК СМЕЖНОСТИ
Матрица смежности
Степень вершины – это количество связанных с ней рёбер (петля считается дважды!).

Варианты изображения графа

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

Что такое дерево?
Дерево – это структура данных, которая служит моделью многоуровневой структуры (иерархии).

Дерево
дерево
ABC ABDC
BCD CCC…

Генеалогическое древо
Родословная А. В. Суворова

Взвешенные графы
Весовая матрица:
вес ребра
12
8
2
5
4
6

Цепь и цикл в графе
Цепь – путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
Цикл - цепь, начальная и конечная вершины которой совпадают.
Сеть - граф с циклом.

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

Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра называю дугами.

Количество путей из А в Ж
1
1
1
1+1+1=3
1
1+1+1+1+3=7
1

Вопросы и задания
1. Постройте матрицу смежности для графа

2. Нарисуйте граф по матрице
Вопросы и задания

3. Определите кратчайший путь между пунктами A и E.
Вопросы и задания

Вопросы и задания
4. На рисунке изображена схема дорог, связывающих торговые точки. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей от точки А до точки К?

Вопросы и задания
5. Грунтовая дорога проходит последовательно через населённые пункты А, B, С и D.
При этом длина грунтовой дороги между А и В равна 40 км, между В и С – 25 км, и между С и D – 10 км.
Между А и D дороги нет. Между А и С построили новое асфальтовое шоссе длиной 30 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге - 20 км/ч, по шоссе - 30 км/ч.