13628-1 (Отображение АСД на СДХ), страница 2

если отношение не обладает свойством 3), то R - предпорядок

Отношение строгого порядка, если в п. 3) (a,b) R (b,a) R

R - линейный порядок, если R определено для a и b и R является строгим порядком.

Некоторое множество частично упорядочено, если на нем зафиксирован некоторый порядок, т.е. на множестве существуют несравнимые величины.

Структура G на множестве M - пара (R,M), где R отношение порядка на множестве M.

Примеры: множество натуральных чисел - структура,

множество слов - структура

Индексация I - отображение M на отрезок [ 1..M].

Абстрактные структуры данных

Строка Граф Дерево Стек Очередь Таблица

Строка

Строка - конечное множество символов с отношением линейного порядка. Значит для каждого символа мы знаем предшествующий и последующий символы.

Примеры строк: текст, формулы без индексов и др.

Свойства строк:

- переменная длина,

- обращение к элементам строки идет в соответствии с отношением линейного порядка, а не в соответствии с индексацией на этом множестве.

(L,M) I: M [1..M]

- часто строка имеет дополнительную структуру - синтаксис.

Операции:

- поиск символа,

- вставка символа,

- удаление символа,

- замена символа.

Граф

Графом гамма называются пары (X,U), где X - множество, U- отношение порядка на X (X - частично упорядоченное множество).

Если U - просто порядок, то граф - ориентирован, в силу свойства антисимметричности.

Если U - предпорядок, то граф неориентированный.

Пару (a,b) соединяют дугой, если пара (a,b) множеству U.

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

: UR

Граф гамма - размеченный, если задано некоторое отображение

: X A, где A - множество меток.

ПРИМЕРЫ: 1) сеть дорог (вес - расстояние, метка - название населенного пункта). Найти кратчайший путь из п.A в п.B.

2) Найти электрические характеристики в различных участках электрической цепи.

Способы задания графа:

- графический,

- применение матрицы смежности

x = n; X...X

.

X

1, (X, X) U

S =

0, (X, X) U

- применение матрицы инцедентности

U...U (дуги)

X

.

X

(Вершины)

1, если X инцендентно U и Xявляется концом дуги U

= -1, если X инцендентно U и Xявляется началом дуги U

0, в противном случае.

Степень вершины - число дуг входящих (в) и выходящих (из) данной вершины (инцендентных данной вершине).

Степень захода (исхода) - число дуг входящих (выходящих) в (из) данную вершину.

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

Последовательность вершин графа X...Xназывается цепью, если для

(X, X) U, т.е. существуют дуги по которым можно перейти от X к X, от X к X и т.д.

Последовательность вершин графа называется путем, если для

(X, X) U или (X, X) U.

Всякая цепь - путь, но не всякий путь - цепь.

Если в цепи X=X, то такая цепь называется цикл.

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

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

Вес пути X ... X - сумма весов дуг этого пути.

(X ... X) = (x, x)

Операции:

- вставить вершину,

- удалить вершину,

- вставить дугу,

- удалить дугу и т.д.

С точки зрения графа строка это цепь.

Дерево

Дерево - связный ациклический граф.

Одна вершина в дереве обязательно имеет степень захода 0. Эта вершина - корень дерева. Листья дерева - вершины, имеющие степень исхода равную 0.

Для любой вершины дерева (кроме корня) степень захода равна 1.

Деревья могут быть ориентированные и неориентированные.

Высота дерева (H) - самый длинный путь из корня к листу.

Рекурсивное определение: Множество из одной вершины - дерево.

Если T ... T - деревья, то

Дерево называется k-ичным, если все вершины имеют степень исхода k.

Дерево называется линейным, степень исхода равна 1.

ЗАДАЧА. Подсчитать количество деревьев, имеющих n вершин.

РЕШЕНИЕ. B - число деревьев из i вершин. Следуя рекурсивному определению дерева:

Дерево совершенное, если любой путь от корня к листу отличается не более чем на 1 от самого длинного пути.

Совершенное дерево из n вершин имеет минимальную высоту.

Свойства совершенных деревьев:

- составляют минимальную часть всех деревьев,

- все пути от корня к листу равноправны.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/