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



Дата11.10.2012
Размер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.

Похожие:

1. Основные понятия и определения iconВопросы к зачету по I полугодию по спецматематике, 8 класс, 2007 Основные понятия и определения
Основные понятия и определения (уметь формулировать, применять, приводить примеры)
1. Основные понятия и определения iconОсновные понятия и определения 4 Линейные пространства 4
Данная работа рассматривает основные понятия, свойства, определения и теоремы, связанные с одним из классов линейных операторов –...
1. Основные понятия и определения iconДенис Александрович Шевчук Автокредит: технологии получения Основные понятия и определения
Для целей настоящего документа используются следующие понятия, определения и сокращения
1. Основные понятия и определения iconОсновные понятия и определения
Цели урока: дать основные понятия о принципах и методах сборки. Научиться составлять технологическую схему сборки
1. Основные понятия и определения iconТема II. Рациональные уравнения глава I. Основные понятия § Область определения равенства
В математике широко используются два вида равенств: тождества и урав-нения, различие между которыми устанавливается с помощью понятия...
1. Основные понятия и определения iconЛекция №13 Тема: "Магнетизм"
Цель лекции: Дать студентам основные понятия и определения, используемые в разделе электромагнетизм: магнитное поле, напряженность,...
1. Основные понятия и определения iconОсновные термины и понятия Вопросы к коллоквиуму
В научной литературе существует несколько подходов относительно определения понятия «методология»
1. Основные понятия и определения iconЭлектрический ток
Цель лекции: Дать студентам основные понятия и определения, используемые в разделе электрический ток: вектор тока, сила тока, сопротивление,...
1. Основные понятия и определения iconТеория информационных процессов и систем. Курс лекций
Основные понятия и определения 7 Основные задачи теории информационных систе
1. Основные понятия и определения icon0,5 1,0 его веса. Основные понятия и определения главные размерения судна
Данная методика применяется для определения массы навалочных грузов, перевозимых водным путем по осадке судна. Снятие и учет осадки...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org