Методическая разработка на тему "Графы"

• 1 слайд

  ЭКЗАМЕНАЦИОННАЯ РАБОТА
  ПО ИНФОРМАТИКЕ
  на тему:
  
  «ОСНОВЫ ТЕОРИИ ГРАФОВ»
  
  автор: Макаров Д.А.
  класс -9Б
  учитель: Панафидина Л.М.
  2012г.
  

• 2 слайд

  Оглавление
  1.Основные понятия теории графов
  2.История возникновения
  теории графов
  3.Загадка Кёнигсберга
  4.Изображение графов на плоскости
  5.Некоторые задачи теории графов
  9.Изоморфные графы
  6.Задача
  7. Применение теории графов
  13. Вопросы
  14. Список литературы
  11. Ориентированные графы.
  12.Примеры графов
  8.Виды графов
  10.Знание графов у учащихся нашей школы
  

• 3 слайд

  Основные понятия теории графов
  Граф – система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (рис.1). Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами. Граф, в котором направление линий не выделяется (все линии
  являются ребрами), называется неориентированным;
  граф, в котором направление линий принципиально
  (линии являются дугами) называется ориентированным.
  Теория графов может рассматриваться как раздел
  дискретной математики (точнее – теории множеств).
  Рис.1 Граф с шестью вершинами и семью рёбрами
  Далее
  

• 4 слайд

  Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов.
  В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами.
  В строгом определении графом называется такая пара множеств G=(V,E),
  где V — подмножество любого счётного множества,
  E — подмножество V×V.
  Граф, который можно начертить так, чтобы его ребра пересекались только в вершинах, называется плоским графом.
  Гранью плоского графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри циклов.
  Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение
  Геометрический граф — плоская фигура из вершин — точек плоскости и рёбер — линий, соединяющих некоторые пары вершин. Может представлять многими способами всякий граф.
  Оглавление
  

• 5 слайд

  История возникновения теории графов
  Начало теории графов датируют 1736 г., когда Л. Эйлер (рис.2) решил популярную в то время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен спустя 200 лет (в 1936 г.) Д. Кенигом.
  Оглавление
  рис.2
  

• 6 слайд

  Загадка кёнигсберга
  Среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем семи мостам через реку, не проходя ни по одному из них дважды? Решить эту задачу пытались как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
  В 1736 году задача о семи мостах заинтересовала выдающегося
  математика, члена Петербургской академии наук Леонарда Эйлера,
  который смог найти правило, пользуясь которым легко определить,
  можно ли пройти по всем мостам, не проходя дважды ни по одному
  из них (в случае семи мостов Кёнигсберга это невозможно).
  На упрощённой схеме части города (графе) (рис.3) мостам соответ-
  ствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа).
  Рис.3 Граф
  кёнигсбергских мостов
  Далее
  

• 7 слайд

  В ходе рассуждений Эйлер пришёл к следующим выводам:
  
  1. Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
  2. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
  3. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
  
  Граф кёнигсбергских мостов имеет четыре (синие) нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
  Оглавление
  

• 8 слайд

  Изображение графов на плоскости
  При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками.
  Одному графу можно сопоставить несколько графических представлений. Изображение призвано показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
  Оглавление
  

• 9 слайд

  Некоторые задачи
  теории графов
  Проблема семи мостов Кёнигсберга.
  Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году.
  Задача коммивояжёра.
  Задача о клике.
  Нахождение минимального стягивающего (остовного) дерева.
  Изоморфизм графов — можно ли путем перенумерации вершин одного графа получить другой.
  Планарность графа — можно ли изобразить граф на плоскости без пересечений ребер (или с минимальным числом слоев, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).
  К теории графов также относится целый ряд математических проблем, не решенных на сегодняшний день.
  Оглавление
  

• 10 слайд

  Изоморфные графы
  Для подсчета числа рукопожатий, совершенных четырьмя товарищами А, Б, В и Г при встрече, можно воспользоваться полным графом с четырьмя вершинами. На рисунке представлено несколько вариантов изображения полного графа с четырьмя вершинами.
  Графы, изображенные на рисунке (рис.3) , дают одну и ту же информацию о совершенных рукопожатиях между четырьмя товарищами. Такие графы называют изоморфными (одинаковыми).
  Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них
  одинаковое количество вершин.
  Если вершины одного графа соединены
  ребром, то и соответствующие им вершины
  другого графа тоже соединены ребром.
  Рис3. Изоморфные графы
  Оглавление
  

• 11 слайд

  Познакомимся с основными понятиями теории графов при решении задачи.
  
  
  
  Задача:
  Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
  Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена.
  
  
  
  
  Далее
  

• 12 слайд

  1. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему
  
  2. Ниже изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом
  
  Количество ребер графа соответствует количеству рукопожатий, совершенных молодыми людьми. Их - 10.
  Следующая задача
  

• 13 слайд

  задача
  В трех различных домах (рис.4) живут три поссорившиеся между собой соседа. Недалеко от их домов имеются три колодца. Можно ли от каждого дома проложить к каждому из колодцев тропинку так, чтобы никакие две из них не пересекались?
  Решение: После проведения восьми тропинок можно убедиться, что провести девятую, не
  пересекающуюся ни с какой из ранее проведенных
  тропинок, не удается.
  Рис.4
  Далее
  

• 14 слайд

  Построим граф, вершины которого (А, Б, В, 1, 2, 3) (рис.5) соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку — ребро графа, не пересекающее остальные ребра, провести нельзя.
  Рис.5
  Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).
  Таким образом, ответ на вопрос задачи будет таким: «Нельзя!»
  Оглавление
  

• 15 слайд

  Знание графов у учащихся нашей школы
  Оглавление
  

• 16 слайд

  Применение теории графов
  1.В химии (для описания структур, путей сложных реакций).
  2.В информатике и программировании (граф-схема алгоритма)
  3.В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
  4.В экономике
  5.В логистике
  6.В схемотехнике
  Далее
  

• 17 слайд

  С помощью графов часто упрощается решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др.
  С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети.
  Помогают графы в решении математических и экономических задач.
  
  Далее
  

• 18 слайд

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

• 19 слайд

  Оглавление
  

• 20 слайд

  Далее
  

• 21 слайд

  Далее
  

• 22 слайд

  Оглавление
  

• 23 слайд

  ориентированные графы
  Граф, у которого все ребра ориентированные,
  называется ориентированным графом (рис.6)
  Ребро графа называется ориентированным ребром,
  если одну из его вершин считать началом, а другую —
  концом этого ребра .
  Степенью выхода вершины ориентированного графа
  называется число ребер, для которых эта вершина является
  началом (число ребер, «выходящих» из вершины).
  Рис.6
  Далее
  

• 24 слайд

  Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину).
  Путем в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер (A1A2, A2A3, ..., Аn-1Аn)
  Ориентированным циклом называется замкнутый путь в ориентированном графе.
  
  Оглавление
  

• 25 слайд

  Вопросы
  1.Сколько ребер нужно провести чтобы достроить граф, изображенный на рисунке до полного?
  А) 1
  Б) 2
  В) 3
  Далее
  Оглавление
  

• 26 слайд

  2. Какой из графов, изображенных на рисунке, не является изоморфным с другими?
  А
  Б
  В
  Далее
  

• 27 слайд

  3.Результаты соревнования, в котором участвовали 6 команд, представлены ориентированным графом на рисунке (стрелка направлена в сторону проигравшей команды). Какая команда победила?
  А
  Б
  В
  Г
  Д
  Е
  Оглавление
  

• 28 слайд

  Список литературы:
  1 Бурков В.Н., Новиков Д.А. Как управлять проектами. М.: Синтег, 1997. – 188 с.
  2 Вагнер Г. Основы исследования операций. М.: Мир, 1972. Т. 1–4.
  3 Емеличев В.А,, Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по
  теории графов. М.: Наука, 1990. – 384 с.
  4 Оре О. Теория графов. М.: Наука, 1968. – 352 с.
  5 Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов.
  Тбилиси: Мецниереба, 1974. – 234 с.
  6 Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении
  организационными системами. М.: Синтег, 2001. – 124 с.
  7 Бурков В.Н., Ланда Б.Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые
  модели и задачи управления. М.: Советское радио, 1967. – 144 с.
  Оглавление
  

• 29 слайд

  Правильно!
  Следующий вопрос
  

• 30 слайд

  Правильно!
  Следующий вопрос
  
  

• 31 слайд

  Правильно!
  Вопросы
  Оглавление
  

• 32 слайд

  Неправильно!
  Следующий вопрос
  Предыдущий вопрос
  

• 33 слайд

  Неправильно!
  Следующий вопрос
  Предыдущий вопрос
  

• 34 слайд

  Неправильно!
  Оглавление
  Вопросы
  Предыдущий вопрос
  

Краткое описание документа:

Данная работа знакомит с теорией и понятием графа. Приведены примеры и области применения графов, а также задачи с использованием графов. В разработке присутствует небольшой тест по изученному материалу, который позволит сразу оценить ученика на уроке Данную информацию можно использовать на уроках информатики и математики при изучении темы «Представление информации»