Графы. Основные понятия. Теория и практика. Графы Презентация на тему графы
Оборудование:
- компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
- компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;
- оборудование доски (тема урока, новые термины). Раздаточный материал.
План урока.
II. Изложение нового материала. (10 мин.)
III. Закрепление материала. Практическая работа. (15-20 мин.)
IV. Подведение итога урока.(2 мин)
V. Домашнее задание.
I. Организационный момент. Актуализация знаний.
Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.
II Изложение нового материала.
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)
С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.
Граф – (от греческого grapho – пишу) - это средство наглядного представления элементов объекта связей между ними. Это замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
Граф – это некоторая информационная модель
Граф состоит из вершин или узлов, связанных дугами или отрезками - рёбрами. Линия может быть направлена, т. е. иметь стрелку (дуга), если не направлена – ребро. Две вершины, соединённые дугой или ребром называются смежными.
Примеры графов (Слайд 4, 5, 6)
Задание 1 (Слайд 7):
Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:
Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.
Можно ли долететь на рейсовых ракетах с Земли до Марса?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Две вершины, соединённые дугой или ребром называются смежными. Каждому ребру или дуге соотносится какое-нибудь число. Число может обозначать расстояние между населёнными пунктами, время перехода от одной вершины к другой и т. д.
Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?
Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?
Представление графов (Слайд 12)
Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.
| Списки дуг | Графическая форма | Табличная форма | ||||||||||||||||
| (АВ; 7), |  |
|
III. Закрепление материалы: учащимся предлагается разделить на группы и выполнить задания. Работая в малой группе, ученики обсуждают модели, основываясь на теоретических знаниях, полученных в начале урока. Тем самым достигается повторение и закрепление материала.
Задание 2 (Слайд 13)
IV. Итог урока
Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)
Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)
Что обозначают ребра графа (Пути, движения, направления)
Приведите пример, где в жизни мы можем с ними встретиться?
Как изображаются графы?
V. Домашнее задание. (Слайд 15)
Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint
на своем компьютере.
Текстовое содержимое слайдов презентации:
Графы и их применение при решении задач Содержание Что такое графСвойства графаИстория возникновения графовЗадача о Кенигсбергских мостахПрименение графовВыводы Что такое граф В математике определение графа дается так:Графом называется непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек.Точки называются вершинами графа, а соединяющие линии – рёбрами. Рёбра графа Вершины графа Дальше Что такое граф Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной. Нечётная степень Чётная степень содержание Свойства графов В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа.Число нечётных вершин любого графа чётно.Во всяком графе с n вершинами, где n≥2, всегда найдутся две вершины с одинаковыми степенями. Свойства графов Если в графе с n вершинами (n>2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени n-1.Если полный граф имеет n вершин, то количество рёбер будет равно n(n-1)/2. Свойства графа Полный граф Неполный граф Свойства графа Ориентированный граф Неориентированный граф Изоморфные графы История возникновения графов Термин "граф" впервые появился в книге венгерского математика Д. Кенига в 1936 г., хотя начальные важнейшие теоремы о графах восходят к Л. Эйлеру. Дальше История возникновения графов Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической. содержание Задача о Кенигсбергских мостах Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Дальше Задача о Кенигсбергских мостах Среди жителей Кенигсберга была распространена следующая задача: можно ли пройти по всем мостам и вернуться в начальный пункт, побывав на каждом мосту только один раз? Дальше Задача о Кенигсбергских мостах Пройти по Кенигсбергским мостам, соблюдая заданные условия, нельзя. Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа. дальше Задача о Кенигсбергских мостах Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то такой граф начертить «одним росчерком» невозможно. содержание Эйлеров граф Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Решая задачу о кенигсбергских мостах, Эйлер сформулировал свойства графа:Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. дальше Эйлеров граф Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. дальше Эйлеров граф Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. дальше Эйлеров граф Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». ? Применение графов С помощью графов упрощается решение математических задач, головоломок, задач на смекалку. дальше Применение графов Задача:Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? дальше Применение графов Решение: А Г В Б Д 1 2 3 4 5 6 7 8 9 10 дальше Применение графов В государстве система авиалиний устроена таким образом, что любой город соединён авиалиниями не более чем с тремя другими, и из любого города в любой другой можно проехать, сделав не более одной пересадки. Какое максимальное число городов может быть в этом государстве? Применение графов Пусть существует некоторый город А. Из него можно добраться не более, чем до трёх городов, а из каждого из них ещё не более чем до двух (не считая А). Тогда всего городов не более 1+3+6=10. Значит всего городов не более 10. Пример на рисунке показывает существование авиалиний. А Применение графов Имеется шахматная доска 3x3, в верхних двух углах стоят два чёрных коня, в нижних – два белых (рисунок ниже). За 16 ходов поставьте белых коней на место чёрных, а чёрных на место белых и докажите, что за меньшее число ходов это сделать невозможно. Применение графов Развернув граф возможных ходов коней в круг, получим, что в начале кони стояли так, как на рисунке ниже: Вывод Графы – это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используются при составлении карт и генеалогических древ. В математике даже есть специальный раздел, который так и называется: «Теория графов». содержание
Приложенные файлы
Граф это конечное множество вершин V и множество ребер R, соединяющих пары вершин, G=(V,R). Мощности множеств V и R равны N и M. Множество ребер может быть пустым. Примеры вершин – объекты любой природы (населенные пункты, компьютерные сети). Примеры ребер – дороги, стороны, линии.
Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Степень вершины – количество инцидентных ей ребер. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам.
Маршрут графа – последовательность вершин и ребер. Маршрут замкнутый (циклический), если начальная и конечная вершины совпадают. Маршрут – простая цепь, если все вершины и ребра различны. Граф связный, если каждая вершина достижима из любой другой. Вершины, не имеющие инцидентных ребер, называются изолированными.
Матрица инциденций
Списки связи
Перечень ребер
Матрица смежности связного взвешенного неориенторованного графа графа
Построение остовного связного дерева минимального веса. Алгоритм Крускала Из графа удаляют все ребра, получается остовной подграф, где все вершины изолированы. Каждая вершина помещается в одноэлементное подмножество. Ребра сортируются по возрастанию весов. Ребра последовательно, по возрастанию их весов, включаются в остовное дерево.
Существует 4 случая: 1) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество; 2) одна из вершин принадлежит связному подмножеству, а другая нет, тогда включаем вторую в подмножество, которому принадлежит первая; 3) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества; 4) Обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.
Пример построения остовного дерева минимального веса для графа GG Выполняемые действия Множество вершин Граф 1Построим остовной подграф с изолированным и вершинами Получим 5 одноэлементных подмножеств: {V 1 }, {V 2 }, {V 3 }, {V 4 }, {V 5 } 2Найдем ребро минимального веса (R 15) и добавим его в остовной подграф Образуем связное подмножество вершин: {V 1,V 5 }. Сохраняем подмножества {V 2 }, {V 3 }, {V 4 }
Выполняемые действия Множество вершинГраф 3Среди оставшихся найдем ребро минимального веса (R 45) и добавим его в остовной подграф Добавим в связное подмножество вершину: {V 1,V 5, V 4 }. Сохраняем подмножества {V 2 }, {V 3 } 4Среди оставшихся найдем ребро минимального веса (R 23) и добавим его в остовной подграф Образуем новое связное подмножество вершин: {V 2,V 3 }. Сохраняем первое связное подмножество {V 1,V 5, V 4 }.
Выполняемые действия Множество вершинГраф 5Среди оставшихся найдем ребро минимального веса (R 25) и добавим его в остовной подграф Объединяем подмножества в одно связное подмножество {V 1,V 5, V 4,V 2,V 3 }. 6Остальные ребра не включаются в граф, т.к. все их вершины уже принадлежат одному связному множеству.
Выполняемые действия Множество вершинГраф 7Получен граф, который: остовной (все вершины включены); связный (все вершины можно соединить маршрутами); дерево (нет циклов); имеет минимальный вес. 8Полученное остовное дерево имеет минимальный вес: R 12 +R 25 +R 15 +R 45 = =80 9 Циклическое число графа G равно γ=m-n+1=8-5+1=4, что соответствует количеству ребер, не включенных в дерево.
Объявление переменных Два целочисленных пятиэлементных массива X и Y для хранения координат вершин графа Целочисленный двумерный массив R для хранения весов ребер графа Целочисленные переменные i, n и k для счетчиков циклов Целочисленная переменная S для хранения суммы весов ребер дерева минимального веса
Генерация случайных координат 5-ти вершин графа (цикл по i). Вычисление весов ребер. Вывод матрицы смежности взвешенного орграфа (вложенные циклы по n и по k) Вывод матрицы смежности взвешенного неориентрованного графа – половины элементов начальной матрицы (начальное значение k=n+1) Тело программы
Коробова Анастасия, студентка гр. 14-ПГС-48Д
В наше время актуально изучение различных методов, свойств и нестандартных применений. Мы рассмотрим применение метода «Граф» в окружающей нас действительности.
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Прежде всего, стоит сказать о том, что графы, о которых пойдет речь, к аристократам былых времен никакого отношения не имеют. Наши «графы» имеют корнем греческое слово «графо», что значит «пишу». Тот же корень в словах «график», «биография».
Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях петербургской Академии наук.
С графами встречаются:
в физике - при построении электрических схем
в химии и биологии – при изучении молекул их цепочек
в истории – при составлении генеалогических древ (родословной)
в географии – при составлении карт
в геометрии – чертежи многоугольников, многогранников, пространственных фигур
в экономике – при решении задач о выборе оптимального пути для потоков грузового транспорта (схем авиалиний, метро, железных дорог)
Теория графов применяется при решении заданий математических олимпиад. Графы придают условиям задачи наглядность, упрощают решение, выявляют сходство задач.
Сейчас в любой отрасли науки и техники встречаешься с графами.
Скачать:
Предварительный просмотр:
Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
Презентация по математике Тема: «Графы» Выполнила Студентка группы 14-ПГС-48Д Коробова Анастасия
Графом называют фигуру, состоящую из точек и линий, связывающих эти точки. Линии называют ребрами графа, а точки - вершинами. Вершины, из которых выходит четное число ребер, называют четными, нечетное число – нечетными. Примеры графов Теория графов
Леонард Эйлер (4 апреля 1707, Базель, Швейцария - 7 сентября 1783, Санкт-Петербург, Российская империя) - швейцарский, немецкий и российский математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук. Эйлер - автор более чем 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближённым вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др.
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной. Закономерность 1. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. (рис. А) Закономерность 2 . Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком »(рис. Б) Эйлеровы графы Б А
Закономерность 3. Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок Задача о кенигсбергских мостах.
Это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Смешанный граф
Взвешенный граф 1 2 4 2 3 A B C D E
Деревом называется любой связный граф, не имеющий циклов. Деревья Деревья
Это (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами. Ориентированный граф
С графами встречаются:
Теория графов применяется при решении заданий математических олимпиад. Графы придают условиям задачи наглядность, упрощают решение, выявляют сходство задач. Сейчас в любой отрасли науки и техники встречаешься с графами.
Спасибо за внимание!