Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Элементы теории графов. Способы обходов графов

Содержание

В основе теории лежит понятие графа.- совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа. Граф
Элементы теории графов. Способы обходов графов.Ищенко М. Н.Лицей – интернат естественных наук В основе теории лежит понятие графа.- совокупность конечного числа точек, называемых вершинами Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась В настоящее время графы эффективно используются в теории планирования и управления, теории Благодаря использованию графов можно упростить решение задач.   «В Кенигсберге есть На практике вершины графа можно использовать для представления объектов, а дуги — Основные понятияОриентированныйграфНеориентированныйграфxyxyВзвешенныйграф Основные понятияСмежныевершиныСмежныерёбраBACDBACD Основные понятияИнциденцияBACD Основные понятияСтепень вершиныв неориентированномграфеСтепень вершины A равна BACD5 Задача сводится к тому, чтобы начертить граф одним росчерком, не отрывая карандашa Пути (маршруты) в графахПуть из A в D:Длина пути из A в D:BACDABD2 Замкнутый путьЦиклBACDABADCAAAABDCA Способы представления графовМатрица смежностиBACD0111 Способы представления графовМатрица инциденций1BACD1100 Способы представления графовСписок смежности Обходы графовПоиск в глубинуBACDABDC Program graf;Var n,v,u: integer;	gr: array [1..30, 1..30] of integer;	nov: array [1..15] of Обходы графовПоиск в ширинуBACDABCD Спасибо за внимание!
Слайды презентации

Слайд 2 В основе теории лежит понятие графа.
- совокупность конечного

В основе теории лежит понятие графа.- совокупность конечного числа точек, называемых

числа точек, называемых вершинами графа, и попарно соединяющих некоторые

из этих вершин линий, называемых ребрами или дугами графа.

Граф


Слайд 3 Первая работа по теории графов, принадлежащая известному швейцарскому

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру,

математику Л. Эйлеру, появилась в 1736 г., связанная с

решением известной головоломки о мостах Кёнигсберга. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики.

Слайд 4 В настоящее время графы эффективно используются в теории

В настоящее время графы эффективно используются в теории планирования и управления,

планирования и управления, теории расписаний, социологии, экономике, биологии, медицине,

географии. Широкое применение находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния и др. Математические головоломки тоже являются частью теории графов.

Слайд 5 Благодаря использованию графов можно упростить решение задач.
«В

Благодаря использованию графов можно упростить решение задач.  «В Кенигсберге есть

Кенигсберге есть остров, называемый Кнейпгоф. Река, омывающая его, делится

на два рукава, через которые перекинуто семь мостов. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?»

Кёненсбергские мосты


Слайд 6 На практике вершины графа можно использовать для представления

На практике вершины графа можно использовать для представления объектов, а дуги

объектов, а дуги — для отношений между объектами.
Л. Эйлеру

удалось ответить на этот вопрос.
Представим, что мосты, соединяющие части города – это рёбра графа, а части города – это вершины графа.

A

A

C

B

D


Слайд 7 Основные понятия
Ориентированный
граф
Неориентированный
граф
x
y
x
y
Взвешенный
граф

Основные понятияОриентированныйграфНеориентированныйграфxyxyВзвешенныйграф

Слайд 8 Основные понятия
Смежные
вершины
Смежные
рёбра
B
A
C
D
B
A
C
D

Основные понятияСмежныевершиныСмежныерёбраBACDBACD

Слайд 9 Основные понятия
Инциденция
B
A
C
D

Основные понятияИнциденцияBACD

Слайд 10 Основные понятия
Степень вершины
в неориентированном
графе
Степень вершины A равна
B
A
C
D
5

Основные понятияСтепень вершиныв неориентированномграфеСтепень вершины A равна BACD5

Слайд 11 Задача сводится к тому, чтобы начертить граф одним

Задача сводится к тому, чтобы начертить граф одним росчерком, не отрывая

росчерком, не отрывая карандашa от бумаги и не проводя

ни одной линии дважды. Но это сделать невозможно, т.к. граф кёнигсбергских мостов имеет четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Кёненсбергские мосты

B

A

C

D


Слайд 12 Пути (маршруты) в графах
Путь из A в D:
Длина

Пути (маршруты) в графахПуть из A в D:Длина пути из A в D:BACDABD2

пути из A в D:
B
A
C
D
A
B
D
2


Слайд 13 Замкнутый путь
Цикл
B
A
C
D
A
B
A
D
C
A
A
A
A
B
D
C
A

Замкнутый путьЦиклBACDABADCAAAABDCA

Слайд 14 Способы представления графов
Матрица смежности
B
A
C
D
0
1
1
1

Способы представления графовМатрица смежностиBACD0111

Слайд 15 Способы представления графов
Матрица инциденций
1
B
A
C
D
1
1
0
0

Способы представления графовМатрица инциденций1BACD1100

Слайд 16 Способы представления графов
Список смежности

Способы представления графовСписок смежности

Слайд 17 Обходы графов
Поиск в глубину
B
A
C
D
A
B
D
C

Обходы графовПоиск в глубинуBACDABDC

Слайд 18 Program graf;
Var n,v,u: integer;
gr: array [1..30, 1..30] of

Program graf;Var n,v,u: integer;	gr: array [1..30, 1..30] of integer;	nov: array [1..15]

integer;
nov: array [1..15] of boolean;
procedure dfs (v: integer);
var u:

integer;
Begin
Readln;
Write (v,’ ’);
nov [v]:=false;
For u:=1 to n do
If (gr[v,u]=1) and (nov[u]) then dfs (u);
End;

Begin
n:=4;
for v:=1 to n do
begin
nov [v]:= true;
Writeln;
For u:=1 to n do begin nov [u]:=true;
Write (‘ gr [‘ ,v,u, ‘ ]=‘);
Read (gr [v,u]);

Размерность массива
n =4

End;
End;
For v:=1 to n do begin
IF nov [v] then dfs (v);
End;
Readln;
End.


Слайд 19 Обходы графов
Поиск в ширину
B
A
C
D
A
B
C
D

Обходы графовПоиск в ширинуBACDABCD

  • Имя файла: elementy-teorii-grafov-sposoby-obhodov-grafov.pptx
  • Количество просмотров: 129
  • Количество скачиваний: 0