Задачи, приводящие к теории графов. Основные понятия и определения.

Нажмите для полного просмотра!

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №2

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №3

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №4

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №5

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №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

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №31

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №32

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №33

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №34

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №35

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №36

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №37

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №38

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №39

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №40

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №41

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №42

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №43

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №44

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №45

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №46

Задачи, приводящие к теории графов. Основные понятия и определения., слайд №47

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Задачи, приводящие к теории графов. Основные понятия и определения.. Доклад-сообщение содержит 47 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Задачи, приводящие к теории графов. Основные понятия и определения.

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

Леонард Эйлер 1707-1783

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 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 не достаточно смежных вершин.