Главная · Управление  · Презентация на тему графы. Графы

Презентация на тему графы. Графы

1 слайд

2 слайд

Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) , в которых он описывал решение головоломок и математических развлекательных задач. Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.

3 слайд

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно. На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: Невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

4 слайд

Существуют 4 группы крови. При переливании крови от одного человека к другому не все группы совместимы. Но известно, что одинаковые группы можно переливать от человека к человеку, т.е. 1 – 1, 2 – 2 и т.д. А также 1 группу можно переливать всем остальным группам, 2 и 3 группу только 4 группе. Задача.

5 слайд

6 слайд

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

7 слайд

Ориентированные графы - орграфы Каждое ребро имеет одно направление. Такие ребра называются дугами. Ориентированный граф

8 слайд

Взвешенный граф Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать, например, расстояние между городами или стоимость перевозки). Вес графа равен сумме весов его рёбер. Таблице (она называется весовой матрицей) соответствует граф. 1 2 4 2 3 A B C D E

9 слайд

Задача Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 9 2) 10 3) 11 4) 12

10 слайд

1. 2. 3. 4. 5. Длина кратчайшего маршрута A-B-C-E-F равна 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2

  • познакомить учащихся с понятием “Граф”, основными принципами его построения;
  • формировать умение выделять отношения, связывающие объекты;
  • развивать внимание, способность к логическому рассуждению;
  • воспитывать взаимопомощь, умение работать в коллективе
  • закрепление полученных знаний на практике
  • развитие памяти, внимания;
  • развитие самостоятельности;
  • воспитание познавательной активности.

    • Оборудование:

    • компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
    • компьютеры с ОС 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),
    А В С
    А 3
    В 4
    С 3 4

    III. Закрепление материалы: учащимся предлагается разделить на группы и выполнить задания. Работая в малой группе, ученики обсуждают модели, основываясь на теоретических знаниях, полученных в начале урока. Тем самым достигается повторение и закрепление материала.

    Задание 2 (Слайд 13)

    IV. Итог урока

    Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)

    Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)

    Что обозначают ребра графа (Пути, движения, направления)

    Приведите пример, где в жизни мы можем с ними встретиться?

    Как изображаются графы?

    V. Домашнее задание. (Слайд 15)

    Количество вершин называется
    порядком графа.
    Количество ребер называется
    размером графа.

    Некоторые термины-1

    - Пусть R=(a,b) – одно из ребер графа. Тогда
    вершины a и b называются концевыми
    вершинами ребра;
    - Концевые вершины одного и того же ребра
    называют соседними;
    - Два ребра называют смежными, если они имеют
    общую концевую вершину;
    - Два ребра называются кратными, если
    множества их концевых вершин совпадают;
    - Ребро называется петлей, если его концы
    совпадают.

    Некоторые термины-2

    - Степенью вершины V обозначается deg(V)
    называется количество ребер, для
    которых эта вершина является концевой;
    - Вершина называется изолированной, если
    она не является концевой ни для одного
    ребра;
    - Вершина называется листом, если она
    является концевой ровно для одного
    ребра. Для листа q очевидно deg(q)=1.

    Пример:

    deg(C)=4
    H1,…H4 - Листья

    Еще пример:

    Города B и Д – изолированные
    вершины; Города Г и Е – листья.

    Полный граф

    Граф называется полным, если любые
    две вершины соединены ребром.
    Сколько ребер у полного графа
    порядка n?
    У полного графа порядка n число ребер
    равно Cn2=n!/(2*(n-2)!) =n*(n-1)/2

    Давайте это докажем…

    Полный граф с двумя вершинами
    содержит одно ребро – это очевидно.
    Подставим n=2 в формулу n*(n-1)/2
    Получим:
    n*(n-1)/2=1
    Формула верна при n=2

    Предположение индукции

    Предположим, что формула верна для
    графа c k вершинами.
    Докажем, что отсюда следует
    справедливость формулы для графа
    c (k+1) вершиной.

    Добавим к полному графу с K вершинами еще одну вершину.

    И соединим ее с первыми K
    вершинами…

    Получим:

    Считаем, сколько получилось ребер…

    K*(K-1)/2 + K
    =
    K*(K+1)/2
    Последнее выражение получается,
    если в формулу n*(n-1)/2 вместо n
    подставить K+1.

    Из предположения справедливости
    утверждения при n=k следует
    справедливость утверждения при
    n=k+1.
    Теорема доказана.

    Примеры полных графов

    Важное уточнение

    Пары, задающие ребра в неориентированном графе, неупорядочены (т.е.
    пары (a,b) и (b,a) не различают-ся)

    Ориентированный граф

    Если ребра графа есть множество
    упорядоченных пар (т.е. (a,b) ≠ (b,a)),
    То граф называется ориентированным
    (или орграфом)
    Как придать понятию ориентации
    наглядный смысл?
    Очень просто – ребра снабжаются
    стрелками (от начала к концу)!

    Пример орграфа

    Смешанный граф

    Смешанный граф – это тройка (V, E, A).
    V – множество вершин;
    E – множество неориентированных
    ребер;
    A- множество ориентированных ребер.
    Кстати, ориентированные ребра
    называются дугами.

    Изоморфизм графов

    Пусть имеется два графа G1 и G2
    Если имеется взаимно-однозначное соответствие F
    между вершинами графов G1 и G2 , такое что:
    - если в графе G1 есть ребро (a,b), то и в графе G2
    есть ребро (F(a),F(b))
    - если в графе G2 есть ребро (p,q), то и в графе G1
    есть ребро (F-1(p),F-1(q))
    то графы G1 и G2 называются изоморфными, а
    соответствие F – изоморфизмом.

    Уточнение

    Для орграфов и смешанных графов
    соответствие F должно сохранять
    ориентацию дуг.

    Необходимое условия изоморфизма

    При каких условиях между элементами
    двух конечных множеств можно
    установить взаимно-однозначное
    соответствие?
    Тогда и только тогда, число их
    элементов одинаково.
    Необходимым условием изоморфизма
    графов является одинаковой число
    вершин.

    Достаточно ли это условие?

    Нет, поскольку вершины могут быть
    соединены по-разному.

    Изоморфны ли эти графы?

    Число вершин одинаково –
    необходимое условие соблюдено…

    Пробуем построить соответствие F…

    Это – не изоморфизм: в G1 есть ребро (A,Д),
    а образы этих ребер в G2 не соединены.

    Другая попытка…

    А это изоморфизм!

    А эти графы изоморфны?

    Увы, нет…

    С точки зрения теории два
    изоморфных графа – это один и тот
    же объект (только, может быть, поразному изображенный…)

    Пути (цепи):

    Путь (цепь) это последовательность
    вершин:
    a1, a2, … , an
    в которой соседние вершины ai и ai+1
    соединены ребрами.
    Длина пути есть число составляющих его
    ребер

    Примеры путей:

    (А, Г, В) и (А, Б, Д) – пути. (А, Б, В) – не путь.

    Понятие пути для орграфа сохраняет
    силу, но нуждается в дополнении –
    соседние вершины в
    последовательности
    a1, a2, … , an
    должны соединяться дугами.

    Циклы

    Цикл – это путь, у которого начальная и
    конечная вершина совпадают.
    Длина цикла есть число составляющих его
    ребер.
    Цикл называется простым, если ребра в нем
    не повторяются.
    Цикл называется элементарным, если он
    простой и вершины в нем не повторяются.

    Компоненты связности

    Вершины произвольного графа можно
    разбить на классы, такие, что для
    любых двух вершин одного класса v1
    и v2 существует путь из v1 в v2
    Эти классы называются компонентами
    связности.
    Если у графа ровно одна компонента
    связности, то граф называется
    связным.

    Машинное представление графов.

    Матрица смежности

    - Занумеруем вершины графа G
    последовательными целыми от 1 до n;
    - Построим квадратную таблицу n×n и
    заполним ее нулями;
    - Если имеется ребро, соединяющее
    вершины i и j, то в позициях (i,j) и (j,i)
    поставим единицы;
    - Полученная таблица называется
    матрицей смежности графа G.

    Пример

    Некоторые очевидные свойства матрицы смежности

    - Если вершина изолирована, то ее строка и
    столбец будут полностью нулевые;
    - Количество единиц в строке (столбце)
    равно степени соответствующей
    вершины;
    - Для неориентированного графа матрица
    смежности симметрична относительно
    главной диагонали;
    - Петле соответствует единица, стоящая на
    главной диагонали.

    Обобщение для орграфа

    Матрицу смежности для орграфа
    можно строить аналогичным
    образом, но, чтобы учесть порядок
    вершин, можно поступить так:
    Если дуга исходит из вершины j и
    входит в вершину k, то в позиции (j,k)
    матрицы смежности ставить 1, а в
    позиции (k,j) ставить -1.

    Матрица инцидентности

    - Занумеруем вершины графа G
    последовательными целыми от 1 до
    n;
    - Построим прямоугольную таблицу с
    n строками и m столбцами (столбцы
    соответствуют ребрам графа);
    - Если j-е ребро имеет концевой
    вершиной вершину k, то в позиции
    (k,j) ставится единица. Во всех
    остальных случаях ставится нуль.

    Матрица инцидентности для орграфа

    - Если j-я дуга исходит из вершины k,
    то в позиции (k,j) ставится 1;
    - Если j-я дуга входит в вершину k, то
    в позиции (k,j) ставится -1.
    - В остальных случаях в позиции (k,j)
    остается нуль.

    Поскольку столбцы матрицы
    инцидентности описывают ребра, то
    в каждом столбце может быть не
    более двух ненулевых элементов

    Пример матрицы инцидентности

    Список ребер

    Еще один способ представления графа
    – двумерный массив (список пар).
    Количество пар равно числу ребер
    (или дуг).

    Пример списка ребер

    Сравнение разных способов представления

    - Список ребер самый компактный, а
    матрица инцидентности наименее
    компактна;
    - Матрица инцидентности удобна при
    поиске циклов;
    - Матрица смежности проще
    остальных в использовании.

    Обход графа

    Обходом графа называется перебор его
    вершин, такой, что каждая вершина
    просматривается один раз.

    Соглашение-1

    Перед выполнением поиска для графа
    с n вершинами заведем массив Chk
    из n элементов и заполним его
    нулями.
    Если Chk[i] = 0, значит i-я вершина еще
    не просмотрена.

    Соглашение-2

    Заведем структуру данных
    (хранилище), в котором будем
    запоминать вершины в процессе
    обхода. Интерфейс хранилища
    должен обеспечивать три функции:
    - Занести вершину;
    - Извлечь вершину;
    - Проверить не пусто ли хранилище;

    Соглашение-3

    Когда вершина j помещается в
    хранилище, она отмечается как
    просмотренная (т.е. устанавливается
    Chk[j]=1)

    Алгоритм обхода-1

    1) Берем произвольную начальную вершину,
    печатаем и заносим ее в хранилище;

    3) Берем вершину Z из хранилища;
    4) Если есть вершина Q, связанная с Z и не
    отмеченная, то возвращаем Z в хранилище,
    заносим в хранилище Q, печатаем Q;
    5) Переходим к п.2

    Алгоритм обхода-2

    1) Берем произвольную начальную вершину и
    заносим ее в хранилище;
    2) Хранилище пусто? Если ДА – конец;
    3) Берем вершину Z из хранилища, печатаем и
    удаляем из хранилища;
    4) Помещаем в хранилище все вершины,
    связанные с Z и еще не отмеченные;
    5) Переходим к п.2

    Какие структуры данных подходят в качестве хранилища?

    - Стек (PUSH – занести; POP – извлечь)
    - Очередь (ENQUE – занести; DEQUE –
    извлечь)
    Обе структуры позволяют проверить
    наличие данных.

    Алгоритм-1 в сочетании со стеком
    называется обходом в глубину
    Алгоритм-2 в сочетании с очередью
    называется обходом в ширину

    Коробова Анастасия, студентка гр. 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

    Деревом называется любой связный граф, не имеющий циклов. Деревья Деревья

    Это (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами. Ориентированный граф

    С графами встречаются:

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

    Спасибо за внимание!