Графы Автор: Баум Маргарита Муниципальное автономное общеобразовательное учреждение Тисульская средняя общеобразовательная школа 1 Руководитель: Пода Надежда.

Презентация:



Advertisements
Похожие презентации
Графы Автор: Баум Маргарита Муниципальное автономное общеобразовательное учреждение Тисульская средняя общеобразовательная школа 1 Руководитель: Пода Надежда.
Advertisements

ЕГО ВЕЛИЧЕСТВО ГРАФ. Введение С дворянским титулом «граф» эту тему связывает только общее происхождение от латинского слова «графио» - пишу. ГРА Ф ИО.
Введение в теорию графов. Введение С дворянским титулом «граф» тему моей работы связывает только общее происхождение от латинского слова «графио» - пишу.
Введение Графы заинтересовали нас своей возможностью помогать в решении различных головоломок, математических и логических задач. Так как мы участвуем.
Проект: «Графы». Цели проекта: изучить теорию «Граф», изучить теорию «Граф», развить навыки самостоятельной работы, развить навыки самостоятельной работы,
Теория Графов Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш.
Определение графа Фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек, называется плоским графом, или.
1. Познакомить слушающих с определением графа. 2. Понять, как решаются задачи с помощью графов. 3. Закономерности, которые необходимо соблюдать при решении.
(вычерчивание фигуры непрерывной линией) Презентация выполнена учеником 6 «А» класса Курасовым Александром Презентация выполнена учеником 6 «А» класса.
Применение теории графов Работу выполнила ученица 8 класса Гончарова Дарья.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ И ЕГО ЭЛЕМЕНТОВ. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ.
Домашнее задание «Применение графа» ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью.
Графы Цели урока Повторить определения, теоремы теории графов Научиться строить графы Научиться применять графы к решению практических задач.
Основные ПОНЯТИЯ ТЕОРИИ ГРАФОВ. Граф И ЕГО СВОЙСТВА ПРИМЕРЫ ГРАФОВ.
Применение графов. С помощью графов упрощается решение математических задач, головоломок, задач на смекалку. дальше.
Муниципальное бюджетное общеобразовательное учреждение Кабановская СОШ Как измерить расстояние между родственниками Автор: Ученица 5б класса Балабойко.
Решение задач с помощью графов. Кенигсбергские мосты Можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?
Математика вокруг нас. Какая наука может быть более благородна, более восхитительна, более полезна для человечества, чем математика? (Франклин).
Элементы теории графов. Способы обходов графов. Лицей – интернат естественных наук.
Работу выполнил ученик 8а класса Кичиков Валерий Кичиков Валерий Учитель Еремеева Н.Н. Учитель Еремеева Н.Н. Работу выполнил ученик 8а класса Кичиков Валерий.
Транксрипт:

Графы Автор: Баум Маргарита Муниципальное автономное общеобразовательное учреждение Тисульская средняя общеобразовательная школа 1 Руководитель: Пода Надежда Степановна

Что такое граф ? В математике определение графа дается так: Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами. Рёбра графа Вершина графа

Как возникли графы? Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической. Термин "граф" впервые появился в книге венгерского математика Д. Кенига в 1936 г., хотя начальные важнейшие теоремы о графах восходят к Л. Эйлеру.

Задача о Кенигсбергских мостах Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз. Пройти по Кенигсбергским мостам, соблюдая заданные условия, нельзя. Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа.

Одним росчерком Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то такой граф начертить «одним росчерком» невозможно.

Что такое гамильтонов путь (цикл) ? ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ ЕГО ВЕРШИНУ ТОЛЬКО ОДИН РАЗ. ГРАФ, СОДЕРЖАЩИЙ ГАМИЛЬТОНОВ ЦИКЛ, НАЗЫВАЕТСЯ ГАМИЛЬТОНОВЫМ. (C, D, A, B, E) – гамильтонов путь A BE C D

Что называют полным графом, а что дополнением графа? ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ. ДОПОЛНЕНИЕМ ГРАФА НАЗЫВАЕТСЯ ГРАФ С ТЕМИ ЖЕ ВЕРШИНАМИ И ИМЕЮЩИЙ ТЕ И ТОЛЬКО ТЕ РЕБРА, КОТОРЫЕ НЕОБХОДИМО ДОБАВИТЬ К ИСХОДНОМУ ГРАФУ, ЧТОБЫ ОН СТАЛ ПОЛНЫМ. ДОПОЛНЕНИЕ ГРАФА ДО ГРАФА

Что такое дерево? Деревом называется связный граф, не имеющий циклов GH E C D F A B G, H, E, B, A - ВИСЯЧИЕ ВЕРШИНЫ ЦИКЛ – ПУТЬ, У КОТОРОГО СОВПАДАЮТ НАЧАЛО И КОНЕЦ. A B C u t s r

Условие задачи. В одном дворе живут четыре друга. Вадим и шофер старше Сергея, Николай и слесарь занимаются боксом, Электрик-младший из друзей. По вечерам Андрей и токарь играют в домино против Сергея и электрика. Определите профессию каждого из друзей.

Начинаем анализировать полученную схему. От каждого верхнего кружка должно исходить 4 линии к кружкам нижнего ряда, одна из которых сплошная(прочная связь), три -пунктирные. (разрывная связь). И от кружков нижнего ряда- аналогично. От Сергея отходит 3 разрывные связи, значит, четвертая- прочная связь Вадим-токарь, Сергей-слесарь, Коля-электрик, Андрей-шофер Ответ готов: слесарьтокарьэлектрикшофер Вадим СергейКоля Андрей

Выводы Графы – это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используются при составлении карт и генеалогических древ. В математике даже есть специальный раздел, который так и называется: «Теория графов».

Используемые материалы