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.


 

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

20287. Сценические эффекты в современном театре 97.5 KB
  ИЗВЕКОВ СВЕТ НА СЦЕНЕ ОЧЕРКИ ПО ИСТОРИИ ОСВЕЩЕНИЯ СЦЕНЫ 1. ИСТОКИ ТЕХНИКИ ОСВЕЩЕНИЯ СОВРЕМЕННОЙ СЦЕНЫ Взаимоотношения между техникой сцены и художественным построением спектакля были подробно рассмотрены в первой части нашей работы Сцена где уже говорилось о том что сценическое освещение являясь одним из технических средств при постановке спектакля одновременно выполняет функцию раскрытия идейного замысла спектакля. Исходным этапом в данном случае должно служить зарождение кулисной сценыкоробки которая во многом продолжает еще...
20288. Художественные искания в западной культуре второй половины XX века 75.5 KB
  Отвергнув возможность преобразования жизни с помощью искусства представители постмодернизма приняли бытие таким какое оно есть сделав искусство предельно открытым наполнили его фрагментами реального жизненного процесса.Хеппенинг Перерастая в искусство постмодернизма €œискусство действия€ приобретает более выраженные формы. ПопАрт В 50ые в США возникло новое крупнейшее направление в современном искусстве – ПОПАРТ – популярное искусство. Бодиарт Бодиарт это искусство тела авангардное направление возникшее в 60х годах.
20289. Жанры средневекового театра 676.5 KB
  Франция Мистерия основной театральный образ Средневековья. Мистерия самая поздняя но и самая полная форма выражения средневековой театральности. Если готический собор застывший образ мироздания то мистерия модель мироздания в действии. Мистерия вбирает в себя все жанры: литургическую драму бытовую драму фарс и соти миракль и моралите.
20290. Новаторство создателей МХТ в области декорационного искусства и технологии 82 KB
  Станиславский Константин Сергеевич Алексеев 17. Опираясь на богатейшую творческую практику и высказывания своих выдающихся предшественников и современников Станиславский заложил прочный фундамент современной науки о театре создал школу направление в сценическом искусстве которое нашло теоретическое выражение в так называемой системе Станиславского. 1877 Станиславский впервые выступил на домашней любительской сцене. Станиславский сыграл десятки комедийных ролей с пением и танцами.
20291. Русская художественная культура 20-х - середины 30-х годов XX века 315 KB
  А русский авангард – своеобразный феномен искусства 20 в. но и с новым искусством стиля модерн – господствующим в это время повсеместно и во всех видах искусства от архитектуры и живописи до театра и дизайна. Русский художник теоретик искусства и писатель. Был членом объединений Мир искусства и Четыре искусства.
20292. Европейский театр классицизма 78 KB
  В основе классицизма лежат идеи рационализма которые формировались одновременно с таковыми же идеями в философии Декарта. Художественное произведение с точки зрения классицизма должно строиться на основании строгих канонов тем самым обнаруживая стройность и логичность самого мироздания. Интерес для классицизма представляет только вечное неизменное в каждом явлении он стремится распознать только существенные типологические черты отбрасывая случайные индивидуальные признаки.
20293. Свет в театре и на эстраде 56.5 KB
  Его история во многом определялась теми источниками света которые имелись в распоряжении театра в те или иные периоды его развития. особенно в его вторую половину стремительно модернизировались новыми техническими возможностями и расширяли сферу применения света как средства сценической выразительности. С точки зрения эстетической искусство сценического света в 17–18 вв.Станиславского партитуры сценического света особенно в чеховских спектаклях на сцене передавались меняющиеся состояния природы утро день вечер ночь; солнечно...
20294. Русская художественная культура середины 50-х - 60-х годов XX века 266.5 KB
  В связи с разоблачением культа личности Сталина происходило преодоление откровенно лакировочного искусства особенно характерного для 30 40х годов. Коммерциализация литературы и искусства привела к распространению произведений не отличающихся высокими художественными достоинствами. В советской культуре наблюдались две противоположные тенденции: искусства политизированного лакирующего действительность и искусства формально социалистического но по существу критически отражающего действительность в силу сознательной позиции художника...
20295. Западно-европейский театр второй половины XIX века 264.5 KB
  Театр XIX в. европейский театр растерял многие свои ценные завоевания. Повсюду в театрах для высшего общества вновь воцарилось величественное но холодное искусство классицизма утратившего после французской революции 1789 1794 гг.