Графом называют фигуру, состоящую из точек и линий, связывающих эти точки. Линии называют ребрами графа, а точки - вершинами. Вершины, из которых выходит. - презентация

1

2 Графом называют фигуру, состоящую из точек и линий, связывающих эти точки. Линии называют ребрами графа, а точки - вершинами. Вершины, из которых выходит четное число ребер, называют четными, нечетное число – нечетными. Если все вершины графа четные, то можно одним росчерком начертить этот граф. При этом движение нужно начинать с любой вершины и окончить в той же вершине. Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной, а заканчивать на другой нечетной вершине. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

3 Через город Кенигсберг, Через город Кенигсберг, ныне Калининград, протекает река Преголя. В XVIII веке в река Преголя. В XVIII веке в городе было семь мостов. городе было семь мостов. Однажды житель города Однажды житель города спросил у своего друга, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать один раз и вернуться побывать один раз и вернуться к тому же месту, откуда к тому же месту, откуда началась прогулка. Ответ на этот вопрос дал Леонард Эйлер. А в1736 году в публикациях Петербургской Академии Наук появилась первая работа Эйлера по теории графов.

4 Математик, механик и физик. Родился в семье небогатого пастора Пауля Эйлера. Эйлер пришел в этот мир в день рождения Леонардо да Винчи Леонардо да Винчи 15 апреля В 1725 два друга Эйлера, сыновья его учителя Даниил и Николай его учителя Даниил и Николай Бернулли, не найдя применения своим силам в Базеле, приняли приглашение только что приняли приглашение только что организованной Академии наук в Петербурге. В Эйлер выступил в журнале «Acta eruditorum» с первыми научными работами, посвященными актуальным задачам об изохроне в сопротивляющейся актуальным задачам об изохроне в сопротивляющейся среде и о траекториях по рекомендации братьев Бернулли его пригласили на одно из свободных мест в Петербургской АН. Он оставил Швейцарию и в мае 1727 приехал в Петербург.

5 1 сорт 2 сорт 3 сорт 4 сорт 5 сорт 1 сорт 2 сорт 3 сорт 4 сорт 5 сорт В пяти корзинах лежали яблоки пяти разных сортов. Яблоки 1-ого сорта лежали в корзинах Г и Д; яблоки 2-ого сорта – в корзинах А, Б, Г; в корзинах А, Б и В лежат яблоки 5- ого сорта, в корзине В к тому же имеются яблоки 4-ого сорта, а в корзине Д – третьего. Пронумеруйте корзины так, чтобы в корзине 1 были яблоки 1-ого сорта, в корзине 2 – второго и тд. В пяти корзинах лежали яблоки пяти разных сортов. Яблоки 1-ого сорта лежали в корзинах Г и Д; яблоки 2-ого сорта – в корзинах А, Б, Г; в корзинах А, Б и В лежат яблоки 5- ого сорта, в корзине В к тому же имеются яблоки 4-ого сорта, а в корзине Д – третьего. Пронумеруйте корзины так, чтобы в корзине 1 были яблоки 1-ого сорта, в корзине 2 – второго и тд. Решение: Составим граф. Решение: Составим граф. А Б В Г Д

6 Чебоксарские мосты: Чебоксарские мосты: Московский мост находиться на заливе. В нашей задаче он будет соединять т.С (Северо- западный р-н) и т. Д(Дом Мод.). Калининский мост построен над оврагом. Здесь он будет соединять т. Д и т. К (Калининский р-н). Гагаринский мост построен через Трусиху. Он будет соединять т.К и т. Л (Ленинский р-н).

7 Решим задачу: Можно ли проехать по всем мостам всего один раз и вернуться в туда откуда начался путь? Решение: Построим граф. Октябрьский мост построен над Чебоксаркой. Он соединяет т. М (ул. Гражданская) и т. С. Сугутский мост лежит над Сугуткой. Здесь он соединяет т. Л и т. М.

8 Граф к задаче: т.М т.С т. Л т. К т.Д Пр. Никольского и Московский пр. ост. Гражданская ост. Фучика Дом Мод Ответ: Все вершины нашего графа четные, значит его можно начертить одним росчерком. ул. Гагарина

9 Графы придают условиям задачи наглядность, упрощают решение, выявляют сходство задач. Сейчас в любой отрасли науки и техники встречаешься с графами: Сейчас в любой отрасли науки и техники встречаешься с графами: Электротехники при построении электрических схем Туркомпании при систематизации маршрутов