Реферат: Структуры данных

вставка символа;

удаление символа;

замена заданного символа другим заданным символом.

3.2. Граф

Определение.

Графом G=(X,U) где X - множество, а U - отношение порядка на X.

Если U - отношение частичного порядка, то G ориентированный граф. Дело в том, что согласно определению частичного порядка из условия (a,b)принадл.U не следует (b,a)принадл.U.

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

Определение.

Граф G - взвешенный если задано отображение m:U -> R. Иногда вес называют длиной дуги.

Определение.

Граф G - размеченный (помеченный) если задано отображение W: X -> A (U->A), где A - множество меток.

Примеры.
Объект Задача
1. Сеть дорог Найти кратчайший маршрут
2.Блок-схема программы Найти неиспользуемый участок
3.Электрическая схема Вычислить характеристики цепи
4.Общество Найти взаимосвязь групп
5.Чертежи Сравнить
6.Химические молекулы Поиск подструктур
7.Сети ЭВМ Найти критический путь
8.Поставка товаров Кто поставляет заданный товар

Способы представления графов.

Графический, матрица смежности, матрица инциденостей.

Определение.

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

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

Определение.

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

Определение.

Последоватедность вершин (x1, x2, x3, ...xN ) графа G называется цепью если для любого i, принадл.[1..n] => {(x(i), x(i+1))принадл.U}.

Последоватедность вершин (x1, x2, x3, ...xN ) графа G называется путем если для любого i, принадл.[1..n] => {(x(i), x(i+1) )принадл.U и (x(i+1), x(i) )принадл.U}. Иными словами путь это цепь, рассматриваемая без учета ориентации вершин.

При этом n - длина пути, цепи соответственно.

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

Если x1=xN в цепи, то цикл называется ориентированным.

Определение.

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

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

Определение.

Весом пути называется m(x1, x2, x3, ...xN) = m(x1, x2) + m(x2, x3) + ... + m(x(N-1), xN).