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.


 

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

32272. Монтажные потоки, схемы монтажа и порядок складирования конструкций одноэтажных промышленных зданий среднего и тяжелого типов 263 KB
  Различают следующие методы монтажа элементов каркаса зданий: раздельный дифференцированный при котором за первую проходку крана устанавливают все колонны; за вторую подкрановые балки и подстропильные фермы с продольными связями а затем фермы и плиты покрытия рис. В последнем случае кран движется вдоль пролета монтируются все колонны а затем перемещается поперек пролета ведется секционный монтаж. Так например при пролете 12 и шаге колонн 6 м движении крана по середине пролета можно с одной стоянки монтировать до 6 колонн или...
32273. Порядок и методы монтажа многоэтажных промышленных зданий. Схемы размещения монтажных кранов, применяемая оснастка 31 KB
  Наиболее распространенными типами промышленных многоэтажных зданий являются типовые двухсекционные четырехэтажные и трехсекционные пятиэтажные здания с полным железобетонным каркасом монтируемые из унифицированных сборных железобетонных элементов: колонн высотой в один этаж ригелей и плит междуэтажных и чердачных перекрытий. Захватными приспособлениями служат: для колонн траверсы и стропы а для балок ригелей и плит перекрытия траверсы с полуавтоматическими стропами. Выверку правильности расположения колонн и фиксацию расстояний между...
32274. Монтаж конструкций многоэтажных зданий с использованием групповых кондукторов и РШИ 93 KB
  Монтаж конструкций многоэтажных зданий с использованиемгрупповых кондукторов и РШИ Монтаж конструкций при использовании групповых кондукторов При наличии групповых кондукторов рис. В каждой ячейке последовательно устанавливают выверяют и закрепляют все элементы каркаса и после этого перемещают кондуктор на следующую стоянку. После установки колонн их раскрепляют хомутами кондуктора осуществляют предварительную точечную сварку укладывают ригели и сваривают их стыки с колоннами укладывают и сваривают распорные плиты с закладными деталями...
32275. Особенности возведения кирпичных зданий - совмещение каменной кладки с работами по монтажу конструкций и устройству монолитных участков. 24 KB
  При замерзании свежей кладки рр в швах быстро теряет свои свва свободн вода превращся в лед увеличиваясь в объеме что влечет дефекты трещины и разрушение шва недостаточн уплотненность. В проц оттаивания швы обжимаются весом вышележащ кладки что вызыв неравномерн осадку здя = трещ дефции. Спбы выполнения кам кладки в зимн услх: 1.
32276. Организация рабочего места каменщиков 405.5 KB
  Рабочее место каменщика при кладке стен включает участок возводимой стены и часть примыкающей к ней площади, в пределах которой размещают материалы, приспособления, инструмент и передвигается сам каменщик. Рабочее место каменщика состоит из трех зон (рис. 1, а, б) : рабочей 1 - свободной полосы вдоль кладки, на которой работают каменщики; зоны материалов
32277. Возведение кирпичных зданий следует осуществлять только поточным методом, предусматривающим деление здания на несколько одинаковых по трудоемкости захваток: по одно-, двух- и трехзахватной системам 67 KB
  Билет 7 Однозахватная система организации работ применяется преимущественно при строительстве небольших в плане односекционных домов при одноэтажном строительстве когда кладку ведут на всю высоту этажа при трехъярусном членении. В этот же день во вторую смену выполняют вспомогательные работы: установку подмостей доставку кирпича на подмости и т. На захватке рабочем участке где выполняют монтажные работы по условиям техники безопасности не могут одновременно работать каменщики и наоборот. В сельскохозяйственном строительстве при...
32278. Организация возведения кирпичных стен 26 KB
  Численность комплексной бригады может изменяться от 20 до 40 человек в зависимости от конструктивных особенностей здания и особенно кладки. При поточном выполнении каменной кладки основные понятия технологии работ имеют свое специфическое определение. Захватка типовая повторяющаяся в плане часть здания с приблизительно равными на данном и последующих за ним участках полсекции секция две секции объемами кладки предоставленная бригаде каменщиков для поточного выполнения работы на целое число смен.
32279. Конструктивных схемы и порядок монтажа конструкций каркасных многоэтажных гражданских зданий 47.5 KB
  Конструктивная схема каркасного здания:1 колонны 2 ригели 3 рядовые плиты перекрытий 4 связеваяплита перекрытий 5 навесные стеновые панели Каркасными рис. 5 сооружают общественные и административные здания. Колонны и ригели образуют несущие рамы воспринимающие вертикальные и горизонтальные нагрузки здания.
32280. Конструктивные схемы и порядок монтажа конструкций многоэтажных гражданских зданий с неполным каркасом и бескаркасных 138 KB
  Бескаркасные здания из кирпича и мелких камней и блоков возводят обычно с продольными несущими рис. В зданиях с поперечными несущими стенами рис. Возводятся также бескаркасные здания у которых несущими являются как поперечные так и продольные стены. Конструктивные схемы бескаркасных зданий с несущими стенами:а продольными б поперечными Бескаркасные крупноблочные здания со стенами из бетонных и других блоков имеют конструктивные схемы с поперечными и продольными несущими стенами рис.