Начало теории графов было положено Леонардом Эйлером в его знаменитом рассуждении о Кенигсбергских мостах в 1736 году Леонард Эйлер родился 15 апреля. - презентация

1

2

3 Начало теории графов было положено Леонардом Эйлером в его знаменитом рассуждении о Кенигсбергских мостах в 1736 году Леонард Эйлер родился 15 апреля 1707 года в семье пастора, жившей в швейцарском городке Базеле В 13 лет поступил на факультет искусств Базельского университета, где преподавалась и математика, и астрономия В 16 лет получил степень магистра искусств В 20 лет Эйлер получил приглашение из Петербургской академии наук Леонард Эйлер ( ) математик, механик, физик и астроном Начальное обучение прошел дома под руководством отца Пауля Эйлера.

4 В городе Кенигсберге (Калининград) было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом ЛАВОЧНЫЙ МОСТ ЗЕЛЕНЫЙ МОСТ КУЗНЕЧНЫЙ МОСТ ДЕРЕВЯННЫЙ МОСТ МЕДОВЫЙ МОСТ ПОТРОХОВЫЙ МОСТ ВЫСОКИЙ МОСТ

5 ЗАДАЧА: Найти маршрут прохождения всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту

6 Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост линией (ребром), соединяющей соответствующие точки. Получился «граф» Рисунок 2Рисунок 1

7 Изучение Кирхгофом электрических цепей привело к разработке им основных понятий и получению ряда теорем, касающихся графов, имеющих вид деревьев Рисунок 1. Электрическая цепь Рисунок 2. Граф, соответствующий данной цепи

8 Предполагается, что любую географическую карту можно раскрасить четырьмя красками таким образом, чтобы никакие две соприкасающиеся страны не были одного и того же цвета В 1850 Фрэнсис Гутри привлекает внимание своего преподавателя математики О. Де Моргана к проблеме раскрашивания карт В 1879 выдающийся английский математик А.Кэли публикует статью, в которой четко формулирует гипотезу четырех красок

9 ПРИМЕР 1: Для раскрашивания стран данной карты достаточно 4 краски ПРИМЕР 2: Для раскрашивания стран данной карты достаточно 3 краски ПУСТЬ: 1- красный цвет, 2- желтый цвет, 3- зеленый цвет, 4-синий цвет

10 Ученый подошел к исследованию графов, имеющих вид деревьев, решая задачи перечисления органических изомеров Способы представления ЭТАНА:

11