PPt4Web Хостинг презентаций

Главная / Математика / Элементы теории графов. Способы обходов графов
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

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


Скачать эту презентацию

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


Скачать эту презентацию



№ слайда 1 Элементы теории графов. Способы обходов графов. Лицей – интернат естественных на
Описание слайда:

Элементы теории графов. Способы обходов графов. Лицей – интернат естественных наук

№ слайда 2 В основе теории лежит понятие графа. - совокупность конечного числа точек, назыв
Описание слайда:

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

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

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

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

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

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

Благодаря использованию графов можно упростить решение задач. «В Кенигсберге есть остров, называемый Кнейпгоф. Река, омывающая его, делится на два рукава, через которые перекинуто семь мостов. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?»

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

На практике вершины графа можно использовать для представления объектов, а дуги — для отношений между объектами. Л. Эйлеру удалось ответить на этот вопрос. Представим, что мосты, соединяющие части города – это рёбра графа, а части города – это вершины графа. B A C D

№ слайда 7 Основные понятия x y x y B A C D 1377 1323 1508 1400 1724 1542 1300
Описание слайда:

Основные понятия x y x y B A C D 1377 1323 1508 1400 1724 1542 1300

№ слайда 8 Основные понятия B A C D B A C D
Описание слайда:

Основные понятия B A C D B A C D

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

Основные понятия B A C D

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

Основные понятия Степень вершины A равна B A C D

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

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

№ слайда 12 Пути (маршруты) в графах B A C D
Описание слайда:

Пути (маршруты) в графах B A C D

№ слайда 13 B A C D
Описание слайда:

B A C D

№ слайда 14 Способы представления графов A B C D A B 1 0 0 1 C 1 0 0 1 D 1 1 1 0 B A C D
Описание слайда:

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

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

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

№ слайда 16 Способы представления графов A: B, D, C B: A, D C: A, D D: A, B, C B A C D
Описание слайда:

Способы представления графов A: B, D, C B: A, D C: A, D D: A, B, C B A C D

№ слайда 17 Обходы графов B A C D
Описание слайда:

Обходы графов B A C D

№ слайда 18 Program graf; Var n,v,u: integer; gr: array [1..30, 1..30] of integer; nov: arra
Описание слайда:

Program graf; Var n,v,u: integer; gr: array [1..30, 1..30] of 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]); 1 2 3 4 Размерность массива n =4 Исходный массив 0 0 0 1 4 0 0 1 1 3 0 1 0 0 2 1 1 0 0 1 4 3 2 1 Результат End;End;For v:=1 to n do begin IF nov [v] then dfs (v);End;Readln;End.

№ слайда 19 Обходы графов B A C D
Описание слайда:

Обходы графов B A C D

№ слайда 20 Спасибо за внимание!
Описание слайда:

Спасибо за внимание!

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru