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.


 

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

53291. Медицина. Здоровий спосіб життя. Необхідні компоненти для здоровя 254.5 KB
  The topic of our lesson is Health Highlights. By the end of the lesson you will be able to understand the gist and details of the text for reading; to talk about medicine, symptoms of disease; to ask how somebody feels himself and answer such questions; to write the rules of healthy life;
53292. Health is above wealth. Giving advice 61.5 KB
  It is necessary to have not only a healthy body but also a healthy brain. You are school-leavers, so it is very important for you to be healthy to finish school and to enter higher educational establishments. Everybody should keep his/her brains in perfect condition, to be on top form for exams.
53293. "Health and Body Care", 5 клас 49 KB
  Today our lesson is devoted to a very important problem. As you know some people are healthy, some people are unhealthy. Health is the most precious things in people's life. We can't buy health, but we can do a lot to keep it. In order to be healthy we should follow some special rules. The series of pictures on the screen will help you to guess what we are going to speak about.
53294. Проектна робота з використанням комп’ютерних технологій як засобу креативного та інтерактивного навчання у 11 класі за підручником 11.5 MB
  ОПИС ПРОЕКТУ Тема проекту: Helthy Wy of Life. Початком роботи над проектами було анкетування учнів яким були поставлені питання: Учням 10 класу – re you going to life to 100 Додаток 1 Учням 11 класів – Do you know the truth or re you plying with fire Додаток 2 Учням 9 класу – re you helthy Додаток 3 Анкети у додатках.Результати анкетування були проаналізовані та зведені у діаграми: Mostly s: You re not very helthy t ll. You re very very helthy person.
53295. Охорона здоров’я 68.5 KB
  Практична мета: формувати комунікативну компетенцію учнів навчаючи їх вмінню вести бесіду про здоровий спосіб життя на основі прочитаного тексту використовуючи вивчену лексику. Освітня мета: ознайомити учнів із основними складовими здорового способу життя. Розвиваюча мета: розвивати комунікативні здібності учнів із залученням форм та методів інтерактивного навчання. Виховна мета: виховувати дбайливе ставлення до свого здоров’я та позитивне відношення до життя формуючи здоров’язберігаючу компетентність учнів.
53296. Healthy eating 39.5 KB
  Развитие способности к комбинированию и трансформированию речевых единиц, способности осуществлять продуктивные речевые действия на английском языке; развивать навыки интерактивного чтения, умения делать выводы.
53297. Healthy lifestyle 40.5 KB
  P1 Drink clean fresh water. Drink at least eight glasses of water every day. Limit soda and caffeine drinks. It is important to eat green and orange vegetables and fruit every day. Fresh vegetables and fresh fruit like bananas and oranges and tomatoes or carrots are the best. P2 Get plenty of rest and sleep. Children need about eight or ten hours of sleep each night. Make time for you self. Walk in the fresh air. Read and listen to soft music.
53298. ДОМАШНІЙ ХІМІЧНИЙ ЕКСПЕРИМЕНТ 63 KB
  Для дослідів буде потрібно невелику кількість овочів, фруктів, харчової соди, оцту, соків, тому, необхідно звернутися до батьків з проханням, не жаліти, якщо дитина зіпсує їх в своїх дослідах, адже вона пізнає навколишній світ, а це - крок у велику науку. Посудом у домашній лабораторії слугуватимуть скляні ампули від пігулок
53299. Характеристика образів повісті Я. Стельмаха «Химера лісового озера, або Митькозавр з Юрківки» 152.5 KB
  Стельмаха Химера лісового озера або Митькозавр з Юрківки. Стельмаха Химера лісового озера або Митькозавр з Юрківки. Стельмаха Химера лісового озера або Митькозавр з Юрківки – Сергієм і Митьком. Які думки у вас виникли коли ви знайшли сандалю що це взуття якогось дослідника якого з’їв Митькозавр.