X

Код презентации скопируйте его

Ширина px

Вы можете изменить размер презентации, указав свою ширину плеера!

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

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

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

Скачать эту презентацию
Cлайд 1
Элементы теории графов. Способы обходов графов. Лицей – интернат естественных... Элементы теории графов. Способы обходов графов. Лицей – интернат естественных наук
Cлайд 2
В основе теории лежит понятие графа. - совокупность конечного числа точек, на... В основе теории лежит понятие графа. - совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.
Cлайд 3
Первая работа по теории графов, принадлежащая известному швейцарскому математ... Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г., связанная с решением известной головоломки о мостах Кёнигсберга. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики.
Cлайд 4
В настоящее время графы эффективно используются в теории планирования и управ... В настоящее время графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния и др. Математические головоломки тоже являются частью теории графов.
Cлайд 5
Благодаря использованию графов можно упростить решение задач. «В Кенигсберге ... Благодаря использованию графов можно упростить решение задач. «В Кенигсберге есть остров, называемый Кнейпгоф. Река, омывающая его, делится на два рукава, через которые перекинуто семь мостов. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?»
Cлайд 6
На практике вершины графа можно использовать для представления объектов, а ду... На практике вершины графа можно использовать для представления объектов, а дуги — для отношений между объектами. Л. Эйлеру удалось ответить на этот вопрос. Представим, что мосты, соединяющие части города – это рёбра графа, а части города – это вершины графа.
Cлайд 7
Основные понятия x y x y Основные понятия x y x y
Cлайд 8
Основные понятия B A C D B A C D Основные понятия B A C D B A C D
Cлайд 9
Основные понятия B A C D Основные понятия B A C D
Cлайд 10
Основные понятия Степень вершины A равна B A C D Основные понятия Степень вершины A равна B A C D
Cлайд 11
Задача сводится к тому, чтобы начертить граф одним росчерком, не отрывая кара... Задача сводится к тому, чтобы начертить граф одним росчерком, не отрывая карандашa от бумаги и не проводя ни одной линии дважды. Но это сделать невозможно, т.к. граф кёнигсбергских мостов имеет четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды. B A C D
Cлайд 12
Пути (маршруты) в графах B A C D Пути (маршруты) в графах B A C D
Cлайд 13
B A C D B A C D
Cлайд 14
Способы представления графов 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 A B C D A B 1 0 0 1 C 1 0 0 1 D 1 1 1 0
Cлайд 15
Способы представления графов B A C D A-B A-C A-D B-D C-D A B 1 0 0 1 0 C 0 1 ... Способы представления графов B A C D 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
Cлайд 16
Способы представления графов A: B, D, C B: A, D C: A, D D: A, B, C Способы представления графов A: B, D, C B: A, D C: A, D D: A, B, C
Cлайд 17
Обходы графов B A C D Обходы графов B A C D
Cлайд 18
Program graf; Var n,v,u: integer; gr: array [1..30, 1..30] of integer; nov: a... 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]); Размерность массива n =4 End; End; For v:=1 to n do begin IF nov [v] then dfs (v); End; Readln; End.
Cлайд 19
Обходы графов B A C D Обходы графов B A C D
Cлайд 20
Спасибо за внимание! Спасибо за внимание!
Скачать эту презентацию
Наверх