Тема 4.3. Базы данных

Графы.

История графов началась в г. Кенигсберг (ныне Калининград). Город располагался на обоих берегах реки Преголь и на двух островах, которые соединялись семью мостами. Знаменитому математику Леонарду Эйлеру предложили решить задачу: можно ли обойти эти мосты, проходя через каждый из них только один раз?

План города можно представить схемой (рис.4.2.6).На этой схеме части города, разделенные рукавами реки, сжаты в точки A,B,C,D - вершины, а мосты представлены линиями a,b,c,d,e,f,g - ребра.

Рис.4.2.6. Схема города

Фигура, состоящая из точек-вершин и соединяющих их линий – ребер, называется графом.

B

A

Рис.4.2.7. Граф

Последовательность ребер графа, в которой каждые два ребра имеют общую концевую точку, причем первое ребро выходит из вершины A, а последнее входит в вершину B, называется маршрутом, или путем, соединяющим вершины A и B.

В этомслучае вершины A и B называются связанными.

Граф называется связным, если любая пара его вершин связна.

Граф, изображенный на рис. 4.2.8. – несвязен.

Рис.4.2.8. Несвязный граф

Маршрут называется цепью, если каждое ребро графа встречается в нем не более одного раза, причем вершины в цепи могут повторяться и несколько раз.

Цепь, начальная и конечная вершины которой совпадают, называется циклом (рис.4.2.9).

Рис.4.2.9. Цикл.

Вершина называется четной, если в ней сходится четное число ребер. Вершина называется нечетной, если в ней сходится нечетное число ребер.

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

Если множество ребер графа конечно, то такой граф называется конечным.

Леонард Эйлер, изучая проблему кенигсбергских мостов, решил общую задачу, которая описывается следующей теоремой.

Теорема Эйлера. В любом конечном связном графе, все вершины которого четны, существует цикл, в котором каждое ребро графа участвует ровно один раз.

Такой цикл называется эйлеровым циклом, а граф, все вершины которого четны - эйлеровым графом.

В задаче о кенигсбергских мостах граф не является эйлеровым, так как все его вершины нечетны.

Эйлеровы циклы обдают тем свойством, что они проходят через каждое ребро графа ровно один раз.

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

Важный класс графов составляют так называемые деревья. Дерево – это связный граф, который не имеет циклов.

Число вершин дерева на единицу больше числа его ребер.

Вопросы для самоконтроля

1 Понятие о данных.

2 Типы данных.

3 Что такое структура данных?

4 Содержание определения структуры данных?

5 Какие структуры относятся к линейным?

6 Что такое массив?

7 Что такое таблица?

8 Что такое стек?

9 Что называется размерностью массива?

10 Какие действия допустимы над массивом?

11 Что такое хеш-таблица и для чего она применяется?

12 Назначение очереди в программировании?

13 Какие структуры данных относятся к нелинейным структурам:?

14 Что такое связные списки?

15 Что такое граф?

16 Какой маршрут называется цепью?

Тесты

1.Совокупность значений определенных ячеек памяти, преобразование которых осуществляется в соответствии инструкциями программы, это

+данные

-команды

-файлы

-пакеты

2. К линейным структурам данных относятся:

+массив

+таблица

+стек

- запись

3. Фигура, состоящая из точек-вершин и соединяющих их линий – ребер, это

- блок-схема

+ граф

- очередь

- дерево

4. Вершина графа может быть

+четной

+нечетной

-острой

-пологой

5 Упорядоченная структура однотипных данных

+ массив

- запись

- файл

- очередь

6. Маршрут, в котором каждое ребро графа встречается в нем не более одного раза

+цепь

- петля

- цикл

- путь

7. Граф, все вершины которого четные, называется

+ эйлеровым

- гамильтоновым

- паскалевым

- правильным

8. Структура данных с методом доступа к элементам LIFO - «последним пришел — первым вышел»)

- очередь

+стек

- цепь

- хеш

9. Структура данных с порядком доступа к элементам FIFO - «первый пришёл — первый вышел»).

-стек

+очередь

- цепь

- цикл

10.Связный граф, не имеющий циклов, это

+дерево

- сеть

- очередь

- поток

Дата добавления: 2014-12-10