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

Доклад раскрывает тему "Элементы теории графов Способы обходов графов ".
Презентация поможет подготовится к предмету Математика, может быть полезна как ученикам и студентам, так и преподавателям.
Материал представлен на 20 страницах, оформлен в виде презентации, доступен для скачивания и просмотра онлайн.

Навигация по документу

Страница №1
Элементы теории графов. Способы обходов графов.
Страница №2
В основе теории лежит понятие графа.
В основе теории лежит понятие графа.
Страница №3
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г., связанная с решением известной головоломки о мостах Кёнигсберга. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г., связанная с решением известной головоломки о мостах Кёнигсберга. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики.
Страница №4
В настоящее время графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния и др.
 Математические головоломки тоже являются частью теории графов.
В настоящее время графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния и др. Математические головоломки тоже являются частью теории графов.
Страница №5
Информация вложена в изображении слайда
Страница №6
На практике вершины графа можно использовать для представления объектов, а дуги — для отношений между объектами.
На практике вершины графа можно использовать для представления объектов, а дуги — для отношений между объектами.
Страница №7
Основные понятия
Основные понятия
Страница №8
Информация вложена в изображении слайда
Страница №9
Информация вложена в изображении слайда
Страница №10
Информация вложена в изображении слайда
Страница №11
Задача сводится  к тому, чтобы начертить граф одним росчерком, не отрывая карандашa от бумаги и не проводя ни одной линии дважды. Но это сделать невозможно, т.к. граф кёнигсбергских мостов имеет четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Задача сводится к тому, чтобы начертить граф одним росчерком, не отрывая карандашa от бумаги и не проводя ни одной линии дважды. Но это сделать невозможно, т.к. граф кёнигсбергских мостов имеет четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Страница №12
Пути (маршруты) в графах
Пути (маршруты) в графах
Страница №13
Информация вложена в изображении слайда
Страница №14
Способы представления графов
Способы представления графов
Страница №15
Информация вложена в изображении слайда
Страница №16
Информация вложена в изображении слайда
Страница №17
Информация вложена в изображении слайда
Страница №18
Program graf;
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;
Program graf; 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;
Страница №19
Информация вложена в изображении слайда
Страница №20
Спасибо за внимание!
Спасибо за внимание!