Информационные модели на графах

Август 21, 2022

Главная
Информатика
Информационные модели на графах

Содержание

2. Его величество Граф Граф – это наглядное средство представления состава и структуры системы. В А С
3. Неориентированный граф Неориентированный граф – это граф, вершины которого соединены ребрами. С помощью таких графов могут
4. Цепь – это путь по вершинам и ребрам графа, включающий любое ребро не более одного раза.
5. Цикл – это цепь, начальная и конечная вершины которой совпадаю. Граф с циклами называют сетью. Анна
6. Ориентированный граф Ориентированный граф – это граф, вершины которого соединены дугами. С помощью таких графов могут
7. Взвешенный граф Взвешенный граф – это граф, у которого вершины или ребра (дуги) характеризуются некоторой дополнительной
8. Что является графом? Схема метрополитена Генеалогическое древо Граф Дракула Компьютерные сети Файловая система Графический редактор Далее
9. Решение задач на графах Задача 1 Сколько трехзначных чисел можно записать с помощью цифр 1, 3,
10. Решение задач на графах Задача 2 На рисунке - схема дорог, связывающих города А, Б, В,
11. Решение задач на графах Задача 3 Между населёнными пунктами A, B, C, D, E, F построены
13. Скачать презентацию

Слайд 2

Его величество Граф
Граф – это наглядное средство представления состава и
структуры

системы.

В

А

С

дуга

ребро

петля

вершина

Слайд 3

Неориентированный граф
Неориентированный граф – это граф, вершины которого соединены ребрами. С

помощью таких графов могут быть представлены схемы двухсторонних отношений.

Анна

Юра

Витя

Маша

Коля

Граф, отражающий отношение «переписываются» между
объектами класса «дети».

Слайд 4

Цепь – это путь по вершинам и ребрам графа, включающий любое

ребро не более одного раза.

Анна

Юра

Витя

Маша

Коля

Слайд 5

Цикл – это цепь, начальная и конечная вершины которой совпадаю. Граф

с циклами называют сетью.

Анна

Юра

Витя

Маша

Коля

Слайд 6

Ориентированный граф
Ориентированный граф – это граф, вершины которого соединены дугами. С

помощью таких графов могут быть представлены схемы односторонних отношений.

Анна

Юра

Витя

Маша

Коля

Граф, отражающий отношение «написал письмо» между
объектами класса «дети».

Слайд 7

Взвешенный граф
Взвешенный граф – это граф, у которого вершины или ребра

(дуги) характеризуются некоторой дополнительной информацией (весом).

Санкт-Петербург

Москва

Нижний Новгород

Екатеринбург

Новосибирск

706

421

1336

1598

Слайд 8

Что является графом?
Схема метрополитена
Генеалогическое древо
Граф Дракула
Компьютерные сети
Файловая система
Графический редактор
Далее

Слайд 9

Решение задач на графах
Задача 1
Сколько трехзначных чисел можно записать с помощью

цифр 1, 3, 5, 7 при условии, что в записи числа не должно
быть одинаковых цифр?

0

1

3

5

7

3

5

7

1

3

5

1

5

7

1

3

7

5

7

3

7

3

5

5

7

1

7

1

5

3

7

1

7

1

3

3

5

1

5

1

3

Ответ: 24 числа

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Слайд 10

Решение задач на графах
Задача 2
На рисунке - схема дорог, связывающих города

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

А

Б

В

Г

Д

Ж

Е

1. А-Б-Д-Ж

2. А-Б-Г-Д-Ж

3. А-Б-Г-Ж

4. А-В-Б-Д-Ж

5. А-В-Б-Г-Д-Ж

6. А-В-Б-Г-Ж

7. А-В-Г-Д-Ж

8. А-В-Г-Ж

9. А-В-Ж

10. А-В-Е-Ж

Ответ: 10 путей

Слайд 11

Решение задач на графах
Задача 3
Между населёнными пунктами A, B, C, D,

E, F построены дороги, протяжённость которых приведена в таблице.. Определите длину кратчайшего маршрута из А в F.

А

B

C

D

E

F

2

4

1

7

3

4

3

2

1. A-B-C-D-E-F
(2+1+3+3+2=11)

2. A-B-C-E-F
(2+1+4+2=9)

3. A-B-E-F
(2+7+2=11)

4. A-C-D-E-F
(4+3+3+2=12)

5. A-C-E-F
(4+4+2=10)

Ответ: 9