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.


 

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

79511. Структура психологической службы 30.76 KB
  Психологический кабинет управления образованием районный городской областной; Практический психолог работающий в образовательном учреждении; Центр психологической службы образования головная организация руководящая деятельностью психологов работающих в образовательных учреждениях психологических кабинетах и специалистов всех психологических служб определенного региона. В Центр могут обращаться родители педагоги другие работники народного образования. Психологические кабинеты отделы при районных областных городских...
79512. Психологическая служба в образовательных учреждениях различного типа 32.14 KB
  Так психопрофилактика предусматривает меры по адаптации воспитанников к широкому социальному окружению за пределами детского дома школы-интерната. В процессе работы необходимо решать вопросы которые обычно не встают так остро перед психологами в массовой школе: взаимоотношений воспитанников со взрослыми и сверстниками в массовой школе с семьями учеников; взаимоотношений воспитанников с родителями и опекунами. Важно также способствовать оптимизации отношений ребенка с официальными опекунами; взаимоотношений воспитанников с шефами и...
79513. Развивающая и психокоррекционная работа 26.8 KB
  Развивающая и психокоррекционная работа может проводиться в процессе специальной работы психолога с отдельными детьми или с группами детей в русле воспитательных мероприятий с участием родителей и других родственников ребенка.
79514. Предмет школьной психологической службы 31.55 KB
  Существует много разных определений предмета школьной психологической службы но единого общепризнанного нет. Только единство этих 4х аспектов и составляет предмет школьной психологической службы. Научный аспект предполагает разработку методологических проблем школьной психологической службы.
79515. Возрастная психология как теоретическая основа курса 26.48 KB
  Мы понимаем школьную психологическую службу как интегральное образование и рассматриваем ее в трех аспектах: как одно из направлений педагогической и возрастной психологии а именно ее теоретикоприкладное направление изучающее закономерности психического развития и формирования личности школьника с целью разработки способов средств и методов профессионального применения психологических знаний в условиях современной школы научный аспект; как психологическое обеспечение всего процесса обучения и воспитания включая составление учебных...
79516. Цель психологической службы образования 29.04 KB
  Ориентация на развитие ребенка определяет основные задачи психологической службы образования: Реализация в работе с детьми возможностей резервов развития ребенка каждого возраста; Развитие индивидуальных особенностей детей интересов способностей склонностей чувств отношений увлечений жизненных планов; Создание благоприятного для развития ребенка психологического климата который определяется одной стороныорганизацией продуктивного общения детей со взрослыми и сверстниками с другой созданием для каждого ребенка на всех этапах...
79517. Становление психологической службы в системе образования в России 35.21 KB
  С начала 1980х годов происходит интенсивное становление психологической службы в системе образования что было обусловлено потребностью общества бурным социальным развитием повышением требований к творческому и нравственному потенциалу личности. Начало развития школьной психологической службы связано с именами таких ученых как А. Основные вехи становления психологической службы образования в России Дата Мероприятия Основные проблемы 1983 Круглый стол журнала Вопросы психологии Анализ результатов экспериментальных попыток создания...
79518. Главные направления и цели деятельности школьной психологической службы 32.56 KB
  Психопрофилактика предполагает: Ответственность за соблюдение в образовательных учреждениях психологических условий необходимых для полноценного психического развития и формирования личности на каждом возрастном этапе: Своевременное выявление таких особенностей ребенка которые могут привести к определенным сложностям отклонениям в интеллектуальном и эмоциональном развитии в поведении и отношениях; Предупреждение возможных осложнений в связи с переходом на следующую возрастную ступень.Психодиагностика это изучение особенностей...
79519. Основные принципы деятельности педагога-психолога 29.62 KB
  Принцип индивидуального подхода к учащемуся основной принцип работы практического психолога в его основе лежат понимание и признание индивидуальности человека как ценности как уникального явления. Принцип целостности предполагает что деятельность психолога и психологической службы образовательного учреждения должна быть ориентирована на целое на систему. Это означает что внимнием психолога должно быть охвачено большинство учащихся.