Без темы
<<  Задачи на теорию чисел Заказчик  >>
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Историческая записка
Историческая записка
Леонард Эйлер
Леонард Эйлер
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задача о Кёнигсбергских мостах
Задача о Кёнигсбергских мостах
Задача о трех домах и трех колодцах
Задача о трех домах и трех колодцах
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Метрические характеристики графа
Метрические характеристики графа
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Степени вершин графа
Степени вершин графа
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
По степенной последовательности можно построить графы
По степенной последовательности можно построить графы
Задача
Задача
Подграфы
Подграфы
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
4
4
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Цепи
Цепи
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Деревья
Деревья
Граф без циклов (ациклический) называется лесом
Граф без циклов (ациклический) называется лесом
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов
Задачи, приводящие к теории графов

Презентация: «Задачи, приводящие к теории графов». Автор: Alex. Файл: «Задачи, приводящие к теории графов.ppt». Размер zip-архива: 1649 КБ.

Задачи, приводящие к теории графов

содержание презентации «Задачи, приводящие к теории графов.ppt»
СлайдТекст
1 Задачи, приводящие к теории графов

Задачи, приводящие к теории графов

Основные понятия и определения.

2 Историческая записка

Историческая записка

Леонард Эйлер (1707-1783)- швейцарец по происхождению. Приехал в Санкт-Петербург в 1727 году. Не было такой области математики XVIII века, в которой Эйлер не достиг бы заметных результатов. Например, решая головоломки и развлекательные задачи, Эйлер заложил основы теории графов, ныне широко используемой во многих приложениях математики. Напряженная работа повлияла на зрение ученого, в 1766 году он ослеп, но и после этого продолжал работу, диктуя ученикам свои статьи. Эйлер умер в 76 лет и был похоронен на Смоленском кладбище Санкт-Петербурга. В 1957 году его прах был перенесен в Александро-Невскую лавру.

3 Леонард Эйлер

Леонард Эйлер

1707-1783

4 Задачи, приводящие к теории графов

Задачи, приводящие к теории графов

Попробуйте нарисовать закрытый конверт одним росчерком, т.е., не отрывая карандаша от бумаги и не проводя дважды один и тот же отрезок. А если конверт распечатать?

5 Задача о Кёнигсбергских мостах

Задача о Кёнигсбергских мостах

Впервые над задачей описанного выше типа задумался Леонард Эйлер после посещения города Кенигсберга (ныне Калининград). В городе было семь мостов через реку Прегель. Гостям города предлагали задачу: пройти по всем мостам ровно один раз. Никому из гостей не удавалось справиться с задачей. Эйлер отметил на карте города по одной точке на каждом берегу реки и на каждом острове. Затем он соединил эти точки в соответствии с расположением мостов. Задача обхода мостов свелась к задаче изображения одним росчерком следующей картинки

A

D

B

C

6 Задача о трех домах и трех колодцах

Задача о трех домах и трех колодцах

Всегда ли можно изобразить граф на плоскости так, чтобы его ребра не пересекались? Впервые этот вопрос возник при решении старой головоломки. Вот как ее описывает Льюис Кэрролл. В трех домиках жили три человека, неподалеку находилось три колодца: один с водой, другой с маслом, а третий с повидлом. Однако хозяева домиков перессорились и решили провести тропинки от своих домиков к колодцам так, чтобы эти тропинки не пересекались. Первоначальный вариант по этой причине их не устраивал.

7 Задачи, приводящие к теории графов
8 Задачи, приводящие к теории графов
9 Задачи, приводящие к теории графов
10 Задачи, приводящие к теории графов
11 Задачи, приводящие к теории графов
12 Задачи, приводящие к теории графов
13 Задачи, приводящие к теории графов
14 Задачи, приводящие к теории графов
15 Задачи, приводящие к теории графов
16 Задачи, приводящие к теории графов
17 Метрические характеристики графа

Метрические характеристики графа

18 Задачи, приводящие к теории графов
19 Задачи, приводящие к теории графов
20 Задачи, приводящие к теории графов
21 Задачи, приводящие к теории графов
22 Задачи, приводящие к теории графов
23 Задачи, приводящие к теории графов
24 Задачи, приводящие к теории графов
25 Степени вершин графа

Степени вершин графа

26 Задачи, приводящие к теории графов
27 Задачи, приводящие к теории графов
28 Задачи, приводящие к теории графов
29 По степенной последовательности можно построить графы

По степенной последовательности можно построить графы

30 Задача

Задача

Существуют ли графы с данной степенной последовательностью? Ответ пояснить. 1) (1;2;3;4); 2) (13;22;3;5); 3) (0;1;2;3;42); 4) (12;23;32;4); 5) (12;32;4). Решение. 1) Не существует, так как все степени различные (смотри теорему 3). 2) Не существует, так как число вершин нечетной степени нечетно, а именно 5 ( смотри теорему 2). 3) Не существует(смотри задачу 1). 4) Построим граф, имеющий данную степенную последовательность 5) Не существует, так как, соединив вершину степени 4 с четырьмя из оставшихся вершин, убеждаемся, что для вершин степени 3 не достаточно смежных вершин.

31 Подграфы

Подграфы

Операции над графами

32 Задачи, приводящие к теории графов
33 4

4

34 Задачи, приводящие к теории графов
35 Задачи, приводящие к теории графов
36 Задачи, приводящие к теории графов
37 Задачи, приводящие к теории графов
38 Цепи

Цепи

Циклы

39 Задачи, приводящие к теории графов
40 Задачи, приводящие к теории графов
41 Задачи, приводящие к теории графов
42 Деревья

Деревья

43 Граф без циклов (ациклический) называется лесом

Граф без циклов (ациклический) называется лесом

44 Задачи, приводящие к теории графов
45 Задачи, приводящие к теории графов
46 Задачи, приводящие к теории графов
47 Задачи, приводящие к теории графов
«Задачи, приводящие к теории графов»
http://900igr.net/prezentacija/ekonomika/zadachi-privodjaschie-k-teorii-grafov-220374.html
cсылка на страницу

Без темы

757 презентаций
Урок

Экономика

125 тем
Слайды
900igr.net > Презентации по экономике > Без темы > Задачи, приводящие к теории графов