1. Основные понятия и определения



жүктеу 35.1 Kb.
Дата07.02.2019
өлшемі35.1 Kb.

1.Основные понятия и определения

Граф G определяется двумя множествами – множеством вершин V и множеством пар вершин E. Пишут G=(V, E). Если пара вершин неупорядочена, то ее принято называть ребром, если упорядочена – дугой. Граф, состоящий только из ребер, называется неориентированным графом. Граф, содержащий только дуги, - ориентированным графом или орграфом.

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

Две вершины v и w, соединенные ребром (v, w), называют смежными вершинами. Если вершины соединены дугой (v, w), то вершина v смежна вершине w, а обратной смежности нет.

Два ребра называют смежными ребрами, если они имеют общую вершину.

Ребро и любая из двух его вершин называются инцидентными.

Любому ребру или вершине может быть присвоен вес. 



Вес вершины – число, которое характеризует вершину,

вес ребра – число, характеризующее отношение между двумя вершинами.

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

Представление графа в виде матрицы смежности.

Матрица смежности А - это матрица размером N*N, где N – число вершин графа.

Элементы матрицы определяются по следующим правилам:



Неориентированный граф: a[i, j] = 1, если существует ребро соединяющее вершины i и j, иначе a[i, j] = 0.

Ориентированный граф: a[i, j] = 1, если существует дуга из вершины i в вершину j, иначе a[i, j] = 0.

В программе определение матрицы смежностей может быть выполнено следующим образом 



Type
Adjacent = array [1..N, 1..N] of Integer;


Var
A: Adjacent;

Представление графа в виде матрицы инцидентности.

Матрица инцидентности Z - это матрица размером N*M, где N – число вершин графа, M – число ребер ( дуг ) графа.

Элементы матрицы определяются по следующим правилам:



Неориентированный граф: z[i, j] = 1, если вершина i инцидентна ребру j, иначе z[i, j] = 0.

Ориентированный граф: z[i, j] = 1, если вершина i начало дуги j,

z[i, j]=-1, если вершина i конец дуги j, иначе z[i, j] = 0.

В программе определение матрицы инцидентности может быть выполнено следующим образом 

Type

TIncidence = array [1..N, 1..M] of Integer;

Var

Z: TIncidence;
Представление графа в виде списков смежных вершин.

Списки смежных – это одномерный массив размером N, содержащий список вершин смежных с данной:

Type
AdjList = array [1..N] of record


Count: Integer; {число элементов в списке}

List: array[1..N] of record {список}

Node:integer; {номер смежной вершины}

W: <тип>; {вес ребра}

end;;

end;

Var
G: AdjList;

Перечень ребер.

Перечень ребер – это одномерный массив размером M, содержащий список вершин инцидентных данному ребру :

Type
BrList = array [1..M] of record


Node1, Node2, {пара вершин, которые связывает ребро }

W: <тип>; {вес ребра}

end;

Var
G: BrList;

Алгоритм поиска.

Вход: Граф G, представленный списком смежных вершин; вершина v1 .

Выход: Тот же граф, но в котором вершины, достижимые из v1 по некоторому пути, помечены.

begin

Q:={v1};

while Q <> пусто  do

begin 
пусть v - произвольный элемент из Q;


удалить v из Q;

пометить v;

for all v' из L(v) do

if v' не помечена then добавить v' к Q;

end
end

Здесь L(v)  - список смежных вершин с текущей вершиной v.

Алгоритм не полностью определен . Необходимо определить , правило по которому выбирается элемент v из Q в цикле while.

Алгоритм поиска в ширину.

Пусть Q - это очередь и удаляется всегда вершина, которая ожидала дольше всех. Введем две переменные F  - первый и L  - последний.


Это правило можно реализовать с помощью следующих действий.

Добавить v к Q                                        Удалить v из Q.
L:=L+1;                                                        v:=Q[F];
Q[L]:=v;                                                        F:=F+1;
Q - массив с |V| элементами. Q пусто тогда и только тогда, когда L=F.
Переменным L и F сначала присваивается значение 0.

Алгоритм поиска в глубину.

Работа с множеством Q производится по принципу последний пришел-первый ушел, т.е. Q - стек.

Введем переменную L - последний.

Этот принцип можно реализовать с помощью следующих действий.



Добавить v к Q                                        Удалить v из Q.
L:=L+1;                                                       v:=Q[L]; 
Q[L]:=v;                                                        L:=L-1
Сначала L := 0. Q пусто тогда и только тогда, когда L=0.

Достарыңызбен бөлісу:


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет