Базы данных и их преобразование

Графы

Пример Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.

Вопрос: Как можно добраться из Репкино в Мышкино?

Составим графическое изображение дорог без учёта их длины

Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.

Дедкино

Кошкино

Мышкино

Репкино

Графом называется объект, который отображает элементный состав системы и структуру связи.

Дедкино

Кошкино

Мышкино

Репкино

Структура графа

Цикл

Ребра

Вершины

Дедкино

Кошкино

Мышкино

Репкино

Другое название графа – сеть.

Дедкино

Кошкино

Мышкино

Репкино

Графы бывают двух видов. 1) Неориентированный – зависимость двусторонняя. Связь при этом называют симметричной

Дедкино

Кошкино

Мышкино

Репкино

Графы бывают двух видов. 2) Ориентированный – зависимость имеет однонаправленная

Пример Составить граф показывающий возможность переливания крови в зависимости от группы

Иерархические структуры (деревья)

• Иерархия – подчиненность или зависимость одного объекта от другого.

Уровни иерархического дерева

1 уровень

2 уровень

3 уровень

4 уровень

Состав иерархического дерева

Виды связей в иерархическом дереве

Предок

Потомок3

Потомок2

Потомок1

Потомок31

Потомок32

Потомок33

Потомок11

Потомок12

Иерархическая структрура в сети Интернет

fr

edu

ru

com

ac

psu

pstu

hydra

mail

www

hidra.psu.ru

www.pstsu.ac.ru

URL - адресация

http://www.pstsu.ac.ru/cgi/bin/kino.htm

ru

fr

com

edu

ac

kino.htm

index.htm

pstu

www

URL - адресация

http://www.pstsu.ac.ru/cgi/bin/

ru

fr

com

edu

ac

kino.htm

index.htm

pstu

www

Российская федерация

Приволжский

Уральский

Приволжский

Центральный

Центральный

Свердловская обл.

Пермская обл.

Московская обл.

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

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

Березники

Березники

Коломна

Коломна

Пермь

Кунгур

Коломна

Пермь

Кунгур

Округ

Город

Область

Свердловская

Уральский

Приволжский

Пермская

Пермская

Приволжский

Пермская

Приволжский

Центральный

Московская

Представление сети в виде двоичной матрицы

Дедкино

Кошкино

Мышкино

Репкино

Поселок

Поселок

Бабкино

Мышкино

Репкино

Кошкино

Дедкино

Бабкино

1

1

1

0

0

Дедкино

1

0

0

1

0

Кошкино

0

1

1

0

1

Репкино

0

1

0

0

0

Мышкино

0

0

0

0

1