34653

Введение в теорию графов

Реферат

Информатика, кибернетика и программирование

Граф – это множество вершин V и множество ребер(дуг) Е. Вершины графа - объекты любой природы; поскольку их должно быть конечное число, то мы будем обозначать их натуральными числами. Ребра (дуги) графа соединяют некоторые из его вершин. Если ребра имеют направление, то граф называется ориентированным (орграфом) – рисунок А; в противном случае он неориентированный.

Русский

2013-09-08

56 KB

5 чел.

Введение в теорию графов.

Граф – это множество вершин V и множество ребер(дуг) Е. Вершины графа - объекты любой природы; поскольку их должно быть конечное число, то мы будем обозначать их натуральными числами. Ребра (дуги) графа соединяют некоторые из его вершин. Если ребра имеют направление, то граф называется ориентированным (орграфом) – рисунок А; в противном случае он неориентированный – рисунок Б.

 

А)

Б)

 

V={1, 2, 3, 4}

Е={(1,2), (1,4), (2,3), (3,1), (4,1), (4,3)}

У орграфа дуга имеет начало и конец.

Дуга, соединяющая вершину с собой, называется петлей (вершина 3 рис.Б имеет петлю)

 

 

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

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

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

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

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

1

2

3

4

1

0

1

0

1

2

0

0

1

0

3

1

0

0

0

4

1

0

1

0

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

Представление графов в виде матрицы смежности. Смотри таблицу: строчки – начало дуг, столбцы – конец дуг. Матрица смежности составлена по рисунку А.

Некоторые алгоритмы работают на взвешенных графах, у которых каждому ребру сопоставлено число (вес ребра) – расстояние, масса и т.д.

Поиск путей в графе:

  •  найти путь между начальной и конечной вершиной (эта задача называется задачей поиска пути в лабиринте) – поиск в ширину, поиск в глубину;
  •  найти минимальный путь между заданными вершинами (алгоритм Дейкстры, алгоритм Флойда);
  •  найти максимальный путь между заданными вершинами;
  •  найти цикл Эйлера:

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

Последовательность вершин через которые проходит искомый маршрут, как и сам маршрут, называется эйлеровым циклом.

Теорема: Цикл Эйлера существует тогда и только тогда, когда в нем нет вершин нечетной степени.

  •  найти цикл Гамильтона:

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

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

  •  поиск минимального остова:

Остовом (каркасом) графа называется его частичный граф типа дерево.




Найти число различных маршрутов из городов Х в
Y.

Program grl;

const

msa: array [1..3,1..2] of integer=((1,1),(1,1),(0,1));

msb: array [1..3,1..2] of integer=((1,0),(1,1),(1,0));

var i,j,k,l:integer;

a,b,c:array[1..3,1..2] of integer;

begin

writeln('Ввод авиамаршрутов:');

for i:=1 to 3 do

for j:=1 to 2 do

begin

if msa[i,j]<>0 then

begin

writeln('авиалинии-X',i,'Y',j);

readln(a[i,j]);

end;

end;

writeln('Ввод водных маршрутов:');

for i:=1 to 3 do

for j:=1 to 2 do

begin

if msb[i,j]<>0 then

begin

writeln('Водных маршрутов-X',i,'Y',j);

readln(b[i,j]);

end;

end;

for i:=1 to 3 do

for j:=1 to 2 do

c[i,j]:=a[i,j]+b[i,j];

writeln('Ответ: способы попадания из городов Х в город Y');

for i:=1 to 3 do

for j:=1 to 2 do

begin

writeln('X',i,'Y',j,'=',c[i,j]);

end; end.

Найти число различных маршрутов из Х в Z через Y

program grl;

var i,j,k,s:integer;

msa,a:array [1..2,1..3] of integer;

msb,b:array [1..3,1..2] of integer;

c:array [1..2,1..2] of integer;

begin

for i:=1 to 2 do

for j:=1 to 3 do

msa[i,j]:=1;msa[1,3]:=0;

for i:=1 to 3 do

for j:=1 to 2 do

msb[i,j]:=1;msb[3,2]:=0;msb[1,2]:=0;

for i:=1 to 2 do

for j:=1 to 2 do

begin

s:=0;

for k:=1 to 3 do

begin

s:=s+msa[i,k]*msb[k,j];

end;

c[i,j]:=s;

end;

writeln('Способ попадания из Х в Z');

for i:=1 to 2 do

for j:=1 to 2 do writeln('X',i,'Z',j,'=',c[i,j]);

end.

Нахождение кратчайшего пути (алгоритм Дейкстры)

program dis;

uses Crt;

const Nmax=50;

var f:text;

name:string[8];

a:word;

i,j,t,n,x,y,min,nmin:integer;

flag,d,predoc,way:array [1..Nmax] of integer;

mv:array [1..Nmax,1..Nmax] of integer;

begin

clrscr;

writeln('введите имя файла:');

readln(name);

assign(f,name);

reset(f);

read(f,a);

n:=a;

writeln('Граф с кол-вом вершин:',n);

for i:=1 to n do

begin

for j:=1 to n do

begin

read(f,a);

mv[i,j]:=a;

if (i<>j) and (a=0)

then mv[i,j]:=255;

write(mv[i,j]:4);

end;

writeln;

end;

read(f,x);

read(f,y);

write('вход-',x,'выход-',y);

close(f);

t:=x;

for i:=1 to n do

begin

flag[i]:=1;

d[i]:=mv[t,i];

predoc[i]:=0;

end;

flag[t]:=0;

for i:=1 to n-1 do

begin

min:=100;

nmin:=t;

for j:=1 to n do

begin

if (flag[j]<>0) and (min>d[j])

then begin

min:=d[j];

nmin:=j;

end;

end;

t:=nmin;

flag[t]:=0;

for j:=1 to n do

begin

if (flag[j]<>0) and (d[j]>mv[t,j]+d[t])

then

begin

d[j]:=mv[t,j]+d[t];

predoc[j]:=t;

end;

end;

end;

writeln;

if d[y]=255 then

begin

writeln('net pyti');

exit;

end

else writeln('длина кратчайшего пути=',d[y]);

{находим путь}

t:=1;

j:=y;

for i:=1 to n do

way[i]:=0;

for i:=1 to n do

begin

if (predoc[j]<>0) then

begin

t:=t+1;

j:=predoc[j];

way[t]:=j;

end;

end;

writeln('Путь:');write(x,' ');

for i:=n downto 1 do

if way[i]<>0 then write(way[i],' ');

write(y);

end.


 

А также другие работы, которые могут Вас заинтересовать

80200. Основные принципы передачи и приема информации 146.5 KB
  В качестве сигнала можно использовать любой физический процесс изменяющийся в соответствии с переносимым сообщением. целесообразно ввести параметры передаваемого сигнала которые являются основными с точки зрения его передачи. Такими параметрами являются длительность сигнала Тс его ширина спектра Fc и динамический диапазон Dc. Длительность сигнала Тс является естественным его параметром определяющим интервал времени в пределах которого данный сигнал существует.
80201. Радиотехнические сигналы. Теория сигналов. Классификация. Основные характеристики сигналов 70.73 KB
  Изменение во времени напряжения, тока, заряда или мощности в электрических цепях называют электрическим колебанием. Используемое для передачи информации электрическое колебание является сигналом.
80202. Спектральное представление сигналов 109 KB
  Представление сигнала в виде ряда может использоваться и как исходное при его описании и анализе. Фурье свел единую функцию трудно поддающуюся математическому описанию к более удобным в обращении рядам гармонических тригонометрических функций которые в сумме дают исходную функцию. Представим периодический сигнал наиболее распространенной в теории сигналов тригонометрической синуснокосинусной формой ряда Фурье...
80203. Случайные сигналы. Корреляционный анализ сигналов 82.5 KB
  Отличительной чертой случайного сигнала является то что его мгновенные значения заранее не предсказуемы. Важно и то что чаще всего наблюдают относительно небольшие отклонения амплитудных значений случайного сигнала от некоторого среднего уровня; чем больше отклонения по абсолютному значению тем реже их наблюдают. Располагая сведениями о вероятностях флуктуации различного уровня удается создать математическую модель случайного колебания приемлемую для детального анализа случайного процесса. называемых реализациями случайного процесса...
80204. Модулированные сигналы 192.5 KB
  Модулированные сигналы Под модуляцией понимают процесс медленный по сравнению с периодом несущего колебания при котором один или несколько параметров несущего колебания изменяют по закону передаваемого сообщения. Получаемые в процессе модуляции колебания называют радиосигналами. В современных цифровых системах передачи информации широкое распространение получила квадратурная амплитуднофазовая или фазоамплитуд ная ФАМ; mplitude phse modultion...
80205. Аналіз ринкових можливостей 123.5 KB
  Аналіз ринкових можливостей План Маркетингові можливості фірми. Маркетингові можливості фірми Будьякій організації слід самій вміти виявляти ринкові можливості. Маркетингова можливість фірми – це найбільш привабливий напрям зосередження маркетингових зусиль за допомогою яких конкретна фірма може досягти найбільших переваг. Ринкові можливості Маркетингові Мета можливості...
80206. Інформація в маркетинговій діяльності 97 KB
  Інформація в маркетинговій діяльності План Система маркетингової інформації Процес маркетингового дослідження Система маркетингової інформації Загальний маркетинговий цикл включає в себе: маркетингові дослідження; планування; організацію маркетингу і контроль маркетингової діяльності. Маркетингова інформаційна система Процес маркетингового дослідження Мета маркетингових досліджень полягає у зв’язку споживачів і виробників шляхом маркетингової інформації для досягнення мети підприємства і визначення шляхів оптимального використання його...
80207. Типи ринків і моделі поведінки споживачів 115 KB
  Процес прийняття рішення про купівлю Етапи сприймання товаруновинки Промисловий та споживчий ринки З погляду маркетингового управління розрізняють два основних типи ринків: споживчий і промисловий. Порівняльна характеристика споживчого і промислового ринків Характеристика Промисловий ринок Споживчий ринок Обсяг збуту Великий Невеликий Обсяг закупок Великий Невеликий Кількість споживачів Невелика Велика Прийняття рішення про закупку Багато людей Небагато Природа покупки Фахова Дилетантська Розміщення споживачів Географічно сконцентроване...
80208. Добір цільових ринків 69 KB
  Добір цільових ринків План Поняття сегментації Критерії ефективної сегментації Основні принципи сегментації ринків Стратегії охоплення ринку Позиціонування товарів Поняття сегментації Будьяка фірма усвідомлює що її товар не може подобатись одразу всім покупцям. В останньому випадку слід зосередитися на частині ринку або сегментах. При сегментації ринку розрізнення а точніше виділення споживачів має відбуватися на основі вияву суттєвих значущих з погляду фірми різниць між групами споживачів при чому таких різниць які справляють...