Слайд 2
![Граф называется связным, если все его вершины соединены между собой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-1.jpg)
Граф называется связным, если все его вершины соединены между собой
Слайд 3
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-2.jpg)
Слайд 4
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-3.jpg)
Слайд 5
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-4.jpg)
Слайд 6
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-5.jpg)
Слайд 7
![История возникновения графов Термин "граф" впервые появился в книге венгерского](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-6.jpg)
История возникновения графов
Термин "граф" впервые появился в книге венгерского математика Д.
Кенига в 1936 г., хотя начальные важнейшие теоремы о графах восходят к Л. Эйлеру.
Слайд 8
![История возникновения графов Основы теории графов как математической науки заложил](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-7.jpg)
История возникновения графов
Основы теории графов как математической науки заложил в 1736
г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.
Слайд 9
![Задача о Кенигсбергских мостах Бывший Кенигсберг (ныне Калининград) расположен на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-8.jpg)
Задача о Кенигсбергских мостах
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель.
В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.
Слайд 10
![Задача о Кенигсбергских мостах Древняя городская легенда гласила, что тот,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-9.jpg)
Задача о Кенигсбергских мостах
Древняя городская легенда гласила, что тот, кто сумеет
обойти весь город, ровно по разу побывав на каждом из семи мостов, обретёт счастье и богатство. Кто только ни пытался это сделать, но никому не удавалось.
Слайд 11
![Я здесь уже был!](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-10.jpg)
Слайд 12
![Задача о Кенигсбергских мостах Пройти по Кенигсбергским мостам, соблюдая заданные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-11.jpg)
Задача о Кенигсбергских мостах
Пройти по Кенигсбергским мостам, соблюдая заданные условия, нельзя.
Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа.
Слайд 13
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-12.jpg)
Слайд 14
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-13.jpg)
Слайд 15
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-14.jpg)
Слайд 16
![Будет ли данный граф Эйлеровым?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-15.jpg)
Будет ли данный граф Эйлеровым?
Слайд 17
![Будет ли данный граф Эйлеровым?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-16.jpg)
Будет ли данный граф Эйлеровым?
Слайд 18
![Эйлеров граф Если все вершины графа четные, то можно не](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-17.jpg)
Эйлеров граф
Если все вершины графа четные, то можно не отрывая карандаш
от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Слайд 19
![Одним росчерком Граф, имеющий всего две нечетные вершины, можно начертить,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-18.jpg)
Одним росчерком
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая
карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Слайд 20
![Одним росчерком Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». ?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/602229/slide-19.jpg)
Одним росчерком
Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».