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.


 

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

35118. ПОВЕРОЧНЫЙ РАСЧЕТ КОТЛОВ-УТИЛИЗАТОРОВ 1.25 MB
  Котёл Г420 предназначен для охлаждения технологических газов с целью конденсации паров серы и получения насыщенного пара в процессе обезвреживания сероводородных газов. Котлыутилизаторы горизонтальные газотрубные с естественной циркуляцией состоят из входной и выходной газовых камер и газотрубного барабана. По ходу газов испарительная поверхность разделена на две отдельные равные ступени. Технологические газы проходят параллельно в каждой ступени входную газовую камеру испарительный пучок и выходную газовую камеру.
35119. Ректификационная колонна непрерывного действия 577.5 KB
  Как правило ректификационные колонны действуют по принципу противотока в целом по всему аппарату в то время как на каждом отдельном участке формирования поверхности контакта фаз схемы взаимодействия фаз могут быть самыми разнообразными. Для обеспечения неравновесных состояний пара и жидкости в нижнюю часть колонны куб подводится теплота а в верхней части колонны теплота отбирается дефлегматор. Жидкая фаза стекает с питающей тарелки вниз и поступает в куб колонны где происходит интенсивное испарение. Образующийся пар подается вниз...
35120. Проектирование сусловарочного апарата для пивоваренного производства 221 KB
  3 Приготовление пивного сусла 1.4 Охлаждение сусла 1. 1 Технологическая схема производства пива Производство пива слагается из следующих этапов:1приём и хранение солода; 2 очистка и дробление солода; 3 приготовление пивного сусла; 4 охлаждение сусла; 5 приготовление дрожжей чистой культуры; 6 главное брожение; 7 дображивание; 8 осветление пива; 9 розлив пива в бутылки и в бочки.3 Приготовление пивного сусла Дроблённый солод смешивается с тёплой водой около 600 С в заторном котле 13.
35121. ШНЕКОВЫЙ ПРЕСС ВПО 20А 1.82 MB
  В качестве исходных данных использовалась схема пресса с нанесенными габаритными размерами и обозначениями. Для кинематического расчета привода использовались данные о мощности двигателя.
35122. ПРОГНОЗИРОВАНИЕ ПРИБЫЛИ ПРЕДПРИЯТИЯ И ЕЕ АНАЛИЗ НА БАЗЕ 1С: БУХГАЛТЕРИЯ 1.52 MB
  Сводка данных, полученная в результате проведения факторного анализа прибыли, позволяет аналитику выявить степень зависимости прибыли по отдельным факторам, чтобы в дальнейшем учитывать эту информацию при планировании прибыли.
35123. Проектирование котла-утилизатора, предназначенного для охлаждения конвертированных газов 364.5 KB
  Рациональное использование топливно-энергетических ресурсов-важнейшая задача, значимость которой все возрастает. Значительная экономия топливно-энергетических ресурсов может быть достигнута при более широком вовлечении в топливно-энергетический баланс страны вторичных энергоресурсов
35124. Розрахунок системи теплопостачання району міста 412.51 KB
  Вибір джерела теплопостачання теплоносія і типу системи теплопостачання. Визначення витрати теплоносія. Тривалість опалювального періоду nв: год Річні витрати тепла на вентиляцію: ГДж рік Річні витрати тепла споживачами: ГДж рік З Вибір джерела теплопостачання теплоносія і типу системи теплопостачання Вибір джерела теплопостачання теплоносія і типу системи теплопостачання залежить головним чином від сумарного теплового навантаження і технологічних споживачів і визначається виходячи з...
35125. Финансовый контроль 79.5 KB
  Понятие и виды финансового контроля. Контрольная функция финансов проявляется в финансовом контроле важнейшем в системе государственного контроля. Специфика финансового контроля состоит в том что финансы одновременно являются объектом и субъектом контроля. В более узком значении контрольная функция состоит в предупреждении и устранении выявленных в результате контроля негативных явлений и фактов дестабилизирующих развитие экономики и финансов наносящих вред интересам государства трудовых коллективов и большинства населения.
35126. Развитие налоговой политики в Республике Беларусь за 2005 год 63.5 KB
  В целях реализации Закона Республики Беларусь €œО бюджете Республики Беларусь на 2005 год€: разработаны и приняты инструктивные документы о порядке исчисления в 2005 году едиными платежами установленных данным законом налогов и сборов взимаемых от фонда заработной платы и из выручки от реализации товаров работ услуг а также о порядке уплаты в 2005 году местных целевых сборов организациями имеющими филиалы представительства и иные обособленные подразделения; определены сроки перечисления в 2005 году налоговыми агентами в доход местных...