Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Элементы теории графов. Способы обходов графов
Содержание
- 1. Элементы теории графов. Способы обходов графов
- 2. В основе теории лежит понятие графа.- совокупность
- 3. Первая работа по теории графов, принадлежащая известному
- 4. В настоящее время графы эффективно используются в
- 5. Благодаря использованию графов можно упростить решение задач.
- 6. На практике вершины графа можно использовать для
- 7. Основные понятияОриентированный граф Неориентированный граф xyxyВзвешенный граф
- 8. Основные понятияСмежные вершины Смежные рёбра BACDBACD
- 9. Основные понятияИнциденция BACD
- 10. Основные понятияСтепень вершины в неориентированном графе Степень вершины A равна BACD5
- 11. Задача сводится к тому, чтобы начертить граф
- 12. Пути (маршруты) в графахПуть из A в
- 13. Замкнутый путь Цикл BACDA B A D
- 14. Способы представления графовМатрица смежности BACD0 1 1 1
- 15. Способы представления графовМатрица инциденций 1 BACD1 1 0 0
- 16. Способы представления графовСписок смежности
- 17. Обходы графовПоиск в глубину BACDA B D C
- 18. Program graf;Var n,v,u: integer; gr: array [1..30, 1..30]
- 19. Обходы графовПоиск в ширину BACDA B C D
- 20. Спасибо за внимание!
- 21. Скачать презентанцию
В основе теории лежит понятие графа.- совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа. Граф
Слайды и текст этой презентации
Слайд 1Элементы теории графов.
Способы обходов графов.
Ищенко М. Н.
Лицей – интернат
естественных наук
Слайд 2В основе теории лежит понятие графа.
- совокупность конечного числа точек,
называемых вершинами графа, и попарно соединяющих некоторые из этих вершин
линий, называемых ребрами или дугами графа.Граф
Слайд 3Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.
Эйлеру, появилась в 1736 г., связанная с решением известной головоломки
о мостах Кёнигсберга. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики.
Слайд 4В настоящее время графы эффективно используются в теории планирования и
управления, теории расписаний, социологии, экономике, биологии, медицине, географии. Широкое применение
находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния и др. Математические головоломки тоже являются частью теории графов.
Слайд 5Благодаря использованию графов можно упростить решение задач.
«В Кенигсберге есть
остров, называемый Кнейпгоф. Река, омывающая его, делится на два рукава,
через которые перекинуто семь мостов. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?»Кёненсбергские мосты
Слайд 6На практике вершины графа можно использовать для представления объектов, а
дуги — для отношений между объектами.
Л. Эйлеру удалось ответить на
этот вопрос.Представим, что мосты, соединяющие части города – это рёбра графа, а части города – это вершины графа.
A
A
C
B
D
Слайд 11Задача сводится к тому, чтобы начертить граф одним росчерком, не
отрывая карандашa от бумаги и не проводя ни одной линии
дважды. Но это сделать невозможно, т.к. граф кёнигсбергских мостов имеет четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.Кёненсбергские мосты
B
A
C
D
Слайд 18Program 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.
![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:](/img/thumbs/6854de8c6aabc6b3ef5365043f47e5b0-800x.jpg "Элементы теории графов. Способы обходов графов Program graf;Var n,v,u: integer; gr: array [1..30, 1..30] of integer; nov: array [1..15]")
Теги
