Конспект урока граф вершина ребро путь
Обновлено: 08.07.2024
Характеристика темы урока. Содержанием темы являются понятия: граф, узлы графа, задачи на вычерчивание фигур одним росчерком.
- Образовательные
- Сформировать понятия граф, узлы графа;
- Показать применение этих понятий при решении различных практических задач:
- задачи на вычерчивание одним росчерком;
- задачи на прохождение всех комнат лабиринта,
- задача о кенигсбергских мостах.
- 2. Воспитательные:
- Организация внимания у учащихся;
- Повышение интереса к предмету;
- Формирование сознательного отношения к труду.
- Культура оформления записей в тетради.
- Развивающие:
Развитие творческих способностей учащихся, умений сравнивать, анализировать, делать выводы.
Методы обучения: эвристический, иллюстративный, исследовательский методы.
- Организационный момент.
- Проверка домашнего задания.
- Изучение нового материала.
- Закрепление нового материала.
- Подведение итогов, домашнее задание.
- Организационный момент.
- Проверка домашнего задания. На предыдущем уроке учащимся были предложены в качестве домашнего задания следующие задачи:
Задача 1. Что получится, если ленту перекрутить на три оборота и склеить.
- Взять бумажную ленту.
- Повернуть один из концов полоски на три оборота, т.е. на 540 градусов.
- Склеить концы ленты.
- Теперь возьмите ножницы и аккуратно разрежьте полоску посередине. Результаты занести в таблицу.
Задача 2. Не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии, требуется начертить фигуры:
При проверке домашнего задания проверяются результаты эксперимента (задание 1), которые учащиеся должны были занести в таблицу.
При проверке задачи 2 выясняется, что с первой частью задания справились практически все учащиеся, но вторую часть задания выполнить не смогли. В чем причина? Не получается вычертить данную фигуру, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии.
- Объяснение нового материала. Формулирование темы, целей, задач урока.
Впервые основы теории графов появились в работе Л.Эйлера, где он описывал решения головоломок и математических развлекательных задач, а широкое развитие теория графов получила с 50-х гг. XX века в связи со становлением кибернетики и развитием вычислительной техники.
Задание 1. Посчитайте, сколько всего на этом графе узлов и сколько ребер?
Задание 2. Найдите на следующем слайде графы и посчитайте количество узлов и количество ребер графа.
Рис. 1 Рис. 2 Рис. 3 Рис. 4
Задание 3. При взгляде на географическую карту сразу бросается в глаза сеть железных дорог, автомобильных дорог. Является ли она графом? Что в этом случае будет узлами, а что – ребрами? Приведите свои примеры графов, которые мы можем встретить в повседневной жизни.
Учитель: графы бывают полными и неполными. Граф называется полным, если каждые два его узла соединены ребрами. В противном случае граф – неполный.
Граф, каждые два узла которого
Задание 4. Найдите на рис. 1- 4 полные и неполные графы. Ответ обоснуйте.
Задание 5. Чем ещё отличается граф на рис. 4 от графов на рис. 1, рис.3?
Учащиеся: на ребрах нанесены стрелки, указывающие направление ребер.
Учитель: Такой граф называют направленным. А можно ли из графов на рис. 1 и рис.3 сделать направленные графы?
Задание 6. Постройте свой граф, который является направленным.
Учащиеся выполняют задание в тетради, учитель, проходя по рядам, просматривает выполнение задания.
Задание 7. Вернемся к домашней задаче №2. Можно ли назвать фигуры – графом?
Назовите количество узлов, подпишите каждый узел. Назовите количество ребер графа. Является ли он полным? Направленным?
Одно из возможных решений задачи под буквой а).
Рис. 5 2 Рис. 6 2
Чем отличаются эти два графа? Учащиеся перечисляют отличия графов.
Учитель: Если мы посмотрим на граф, то можно заметить, что в узлах соединяется разное количество ребер. В узле 1 на рис. 5 соединяются три ребра, в узле 2 – два ребра.
Узел, в котором соединяется четное число ребер называют четным, а нечетное – нечетным. 1 узел – нечетный, 2 узел – четный.
Задание 8. Перечислите по рис.5, рис.6 четные и нечетные узлы.
Помимо всех перечисленных отличий, у этих графов есть еще одно очень важное отличие, из-за которого первый граф можно вычертить указанным способом, а второй – нет. Зная его, можно по виду графа или фигуры определить можно его вычертить одним росчерком или нет. Чтобы отыскать это свойство графа, предлагаю вам выполнить следующую лабораторную работу. На столах имеются заготовки таблиц. В первом столбике изображены графы. Необходимо подсчитать количество четных и нечетных узлов и результаты подсчетов занести в таблицу .
Учащиеся. Выполняют лабораторную работу, результаты заносят в таблицу.
Можно ли вычертить фигуру, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии
Количество четных узлов
Количество нечетных узлов
После заполнения таблицы учащиеся совместно с учителем проверяют результаты эксперимента, выдвигают гипотезы о количестве узлов, которое необходимо, чтобы можно было вычертить одним росчерком фигуру. Как правило, учащиеся выдвигают много гипотез. Если учащиеся не заметили, то учитель обращает внимание на два факта: по результатам лабораторной работы число нечетных узлов во всех случаях в таблице четно
Свойство. Если в фигуре (на графе) число нечетных узлов больше двух, то её нельзя нарисовать одним росчерком!
Свойство 2. Число нечетных узлов графа всегда четно.
Учитель. Давайте теперь вернемся к домашней задаче №2 и проверим количество нечетных узлов в фигурах.
Рис. 7 2 Рис. 8 2
На рис. 7 нечетные узлы – 1, 3, т.е. всего их два. На рис. 8 нечетные узлы – 1, 3, 7, 6, т.е. – четыре. Во втором случае число нечетных узлов больше двух, поэтому вторую фигуру нельзя нарисовать одним росчерком!
- Закрепление изученного материала.
- Можно ли одним росчерком вычертить фигуры, изображенные на слайде и почему?
Решение. Первую фигуру указанным способом вычертить нельзя (число нечетных узлов больше двух), вторую – можно.
Учитель. Долго бы спорили жители города, если бы через Кенигсберг не проезжал Леонард Эйлер. Он заинтересовался спором и … разрешил его. А сможете ли это сделать вы?
Решение. План города для решения этой задачи можно изобразить графом, который будет иметь четыре узла графа – это берега A и D, острова В и С; 7 ребер – мосты 1 – 7. Если бы существовал искомый маршрут, то этот граф можно было бы вычертить одним росчерком. Чего сделать нельзя, так как количество нечетных узлов больше двух.
- На слайде изображен план подвала из десяти комнат. Можно ли пройти через все двери всех комнат, запирая каждый раз ту дверь, через которую вы проходите? С какой комнаты надо начинать движение?
Решение. Необходимо начать с нечетного узла.
- Подведение итогов, домашнее задание .
- Можно ли начертить фигуры одним росчерком. Если да, то как это сделать?
Задачи, решаемые с помощью теории графов.
- Почтальон Печкин разнес почту во все дома деревни, после чего зашел с посылкой к дяде Федору. На рисунке показаны все тропинки, по которым проходил Печкин, причем, как оказалось, ни по одной из них он не проходил дважды. Каков мог быть маршрут почтальона Печкина? В каком доме живет дядя Федор?
2. Кто играет Ляпкина-Тяпкина?
- Ляпкиным-Тяпкиным буду я! – решительно заявил Гена.
- Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима. – С раннего детства мечтал воплотить этот образ на сцене.
- Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.
- …А мне – Осипа – не уступил ему в великодушии Дима.
- Хочу быть Земляникой или Городничим, - сказал Вова.
- Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно.
Удастся ли распределить роли так, чтобы исполнители были довольны? (Мы не спрашиваем, будут ли довольны зритель.)
3. Корзины, полные хлебцов.
В пяти корзинах лежат хлебцы пяти сортов. Хлебцы первого сорта лежат в корзинах Г и Д; хлебцы второго сорта – в корзинах А, Б и Г; в корзинах А, Б и В имеются хлебцы пятого сорта, в корзине В имеются к тому же хлебцы четвертого сорта, а в корзине Д – третьего. Требуется дать каждой корзине номер, но так, чтобы в корзине № 1 были хлебцы первого сорта (хотя бы один), в корзине № 2 – второго и т.д.
4. Первенство классов.
В первенстве класса по настольному теннису принимали участие 6 учеников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?
5. Задача о трех домах и трех колодцах.
Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году (см. рис.).
6. Задача о четырех красках.
Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 12).
7. Задачи Дьюдени.
2. М-р Робинсон живет в Лос-Анджелесе.
3. Кондуктор живет в Омахе.
4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.
5. Пассажир – однофамилец кондуктора живет в Чикаго.
6. Кондуктор и один из пассажиров, известный специалист по математической физике, хотя в одну церковь.
7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.
Как фамилия машиниста? (рис.13)
Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы).
Описание разработки
Задачи занятия:
учить определять граф по словесному описанию отношений между объектами.
развивать логическое мышление, внимания, воображение, умение анализировать, сравнивать, обобщать.
воспитывать интерес у учащихся к предмету, коммуникативные навыки.
План занятия:
Закрепление пройденного материала
Этап получения новых знаний.
Этап закрепления нового материала.
Этап обобщения знаний.
Ход занятия.
1. Организационный этап.
Друзья, я очень рада
Войти в приветливый ваш класс.
И для меня уже награда
Улыбки ваших милых глаз.
Я знаю: каждый в классе гений,
Но без труда – талант не впрок.
Скрестите шпаги ваших мнений –
Мы вместе сотворим урок.
2. Закрепление пройденного материла.
3. Этап получения новых знаний.
Подумайте, на что похожа эта карта? На карту дорог, на план, на схему.
А если мы эту карту немного преобразим. Например, вот так…
Такие схемы в математике и информатике называются графом.
Как вы думаете, чем граф отличается от карты? На нём нет ничего, кроме точек и линий.
Точки называются вершинами графа.
А линии, которые связывают вершины, называются рёбрами графа.
Значит, граф – это множество точек, которые могут соединяться линиями. Линия указывает на связь между двумя точками.
4. Этап закрепления нового материала.
А давайте рассмотрим ещё одну карту и описание к ней.
Кто ходит в гости по утрам, Тот поступает мудро. Известно всем, тарам-парам, На то оно и утро! Чья эта песенка?
Мы знаем, Винни-Пух очень любит ходить в гости. Вини-Пух вышел рано утром из дома, зашёл в гости к Сове, потом к Кролику. Затем зашёл в лес собрал грибов, около озера поговорил с Осликом Иа, а потом зашёл в гости к Пятачку.
Давайте построим граф, который будет отображать утренний маршрут Винни-Пуха.
Давайте подумаем, какие объекты будут вершинами графа? Дом Винни-Пуха, Сова, Кролик, лес, Ослик Иа, Пятачок. Обратите внимание, что вершины обозначены заглавными буквами, и каждая вершина имеет своё обозначение.
А теперь надо соединить вершины так, чтобы рёбра графа отображали путь, по которому шёл Винни-Пух. Итак. Винни-Пух вышел из дома и зашёл в Сове, значит, соединяем эти две вершины.
После Совы Винни-Пух зашёл к Кролику, соединяем вершины Сову и Кролика. Затем зашёл в лес, к Ослику Иа и к Пятачку. Граф построен, и весь путь Винни-Пуха отображён.
Весь материал - в архиве.
-75%
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
Технологическая карта изучения темы
Личностные УУД:
-иметь познавательный интерес к предмету
-способность к самооценке на основе критерия успешности учебной деятельности
Регулятивные УУД:
-осознавать, принимать и сохранять учебную задачу, участвовать в ее решении
-осуществлять контроль за выполнением действий
-использовать речь для регуляции своих действий
Познавательные УУД:
- извлекать информацию из схем, иллюстраций, текстов
- выявлять особенности объектов
- обобщать и классифицировать объекты по признакам
Коммуникативные УУД:
-участвовать в диалоге
-слушать и понимать речь других
-уметь с достаточной полнотой и точностью выражать мысли
-задавать вопросы и отвечать на вопросы
Технология изучения
-овладеть умением прогнозировать
-слушать и понимать речь других
-уметь достаточно точно выражать свои мысли
-владеть диалогической формой речи
-Здравствуйте, ребята! Я рада видеть вас снова на уроке информатики. Сейчас я прочитаю вам стихотворение, а вы послушайте.
- Прозвенел уже звонок,
Сядем тихо и не слышно
И скорей начнем урок.
Будем изучать, трудиться,
Ведь заданья нелегки.
Вам, друзья, нельзя лениться,
Так как вы ученики!
-Как вы думаете, почему это важно?
Выскажите свои мысли.
-Настроение у всех хорошее? Тогда начнем наш урок. Откройте, пожалуйста, свои тетради и запишите сегодняшнее число. Записали? Отложите ручки в сторонку.
Ребята проверяют свое учебное место.
Дети высказывают свои предположения о необходимости организации своего рабочего места.
Этап актуализации опорных знаний
-отвечать на вопросы
-выражать свои мысли
-Скажите, пожалуйста, что мы делали на предыдущем уроке, ребята?
- Что же такое множество?
-Как называются объекты, которые принадлежат множеству?
-А почему некоторые множества мы называем подмножествами?
-Хорошо, ребята, приведите примеры множеств и подмножеств.
-В третьем классе вы познакомились с графами. Вспомним, что же такое граф?
-А для того, чтобы нам было проще вспомнить, что такое граф, предлагаю вам решить такую задачу.
-Как удобнее решить эту задачу?
-Мы вспоминали, что такое множество, что такое подмножество, что называется элементами множества.
-Множеством называют объединение объектов на основе каких-то общих признаков или свойств.
-Потому что все его элементы принадлежат другому, более крупному множеству.
Ученики приводят свои примеры.
Дети вспоминают определение.
(один ученик идет к доске и решает задачу, остальные выполняют чертеж в тетрадях)
-Вот какая схема у нас получилась. Теперь нам будет намного легче найти решение задачи. Сколько же всего было сделано рукопожатий?
-Молодцы, ребята, совершенно верно.
-Догадались, как называется эта схема?
Конечно, граф. Найдем у графа его вершины
и ребра, и посчитаем, сколько их.
- 6 рукопожатий.
Дети называют вершины (точки 1, 2, 3, 4) и ребра (отрезки, их соединяющие - 6).
Этап постановка учебной задачи
-формировать учебную задачу
-связь между целью деятельности и ее мотивом
-отвечать на вопросы
-выражать свои мысли
-Сегодня на уроке мы откроем новый секрет про графы. Хотите узнать, какой?
-Тогда посмотрите, пожалуйста, на доску.
(на слайде картинка с котом и мышкой). С нами сегодня герои одной стихотворной сказки: кот КотАуси, мышка Мауси и ее друзья. Мауси и ее друзья: Ник, Джек и Пухлик решили соединить свои норки подземными ходами, чтобы свободно перемещаться и не попадаться на глаза Котауси. Для этого они обозначили каждую нору и дом кота числом букв в имени хозяина каждого домика. Какими числами обозначены их дома?
-Хорошо. Дальше каждый из них задумал свой собственный план строительства ходов. Попробуем рассекретить, как выглядит план каждого мышонка и кота Котауси. Для этого я раздам вам листочки, на которых изображено множество точек, расположение элементов которого соответствует расположению норок мышат и кота. Что нам с вами нужно сделать? Как вы будете его изображать?
На прошлом уроке мы уже говорили о том, что одним из методов познания является моделирование, рассматривали различные классификации моделей и выделили в качестве предмета нашего рассмотрения информационные модели. Среди них можно выделить графические информационные модели, к которым относятся карты, чертежи, схемы, диаграммы, графики и предмет сегодняшнего рассмотрения — графы.
Если рассматривать группу объектов вместе с имеющимися между ними связями как единое целое, то можно говорить о системе. Мы можем графически изобразить объекты системы вершинами, а связи между ними линиями (рёбрами). В этом случае мы получим информационную модель системы в форме графа.
Если рёбра графа имеют направление, то оно отображается стрелками, а граф называется ориентированным (направленным).
Вершины графа могут отображаться точками, кругами, прямоугольниками и т.д.
Если вершины или ребра графа характеризуются некоторой дополнительной информацией — весом вершины или ребра, то такой граф называют взвешенным.
С помощью взвешенных графов удобно изображать дороги между населенными пунктами. Например, в приведенном примере указана протяжённость дорог в километрах.
Проведём путь, проходящий по вершинам и ребрам графа так, чтобы любое ребро входило в него не более одного раза. Такой путь называется цепью. Цепь, у которой совпадают начальная и конечная вершины, называется циклом.
Граф с циклом называется сетью . Если персонажей некоторого литературного произведения, мультфильма или сериала представить вершинами графа, а связи между ними изобразить рёбрами, то получится граф, который называют семантической сетью.
Информационные модели в виде графов широко используются в повседневной жизни.
Например, при проектировании нового жилого района можно здания обозначить как вершины графа, а дороги, коммуникации и т.д. — ребрами графа. По таким графам удобно, например, прогнозировать загрузку дорог и находить оптимальные транспортные маршруты. Другим примером является схема метрополитена. Вершинами в графе в этом случае являются станции метро.
Граф, в котором отсутствуют циклы, называется деревом.
В этом случае между любыми двумя вершинами существует только один путь.
С помощью дерева удобно представлять иерархическую систему.
У дерева выделяется одна главная вершина, которую называют корнем.
Каждая вершина дерева, исключая корень, может иметь только одного предка (вершина верхнего уровня), но при этом может порождать множество потомков, отображаемых вершинами нижнего уровня. Вершины, у которых отсутствуют порожденные вершины, называются листьями.
Одним из известных применений графов является генеалогическое или родословное дерево, на котором отображаются родственные связи.
Существуют задачи, которые удобно решать с помощью графов.
Например, если мы хотим отобразить все возможные варианты трехзначных чисел, которые могут получиться из цифр 7 и 8.
С помощью графов удобно решать задачи на определение выигрышной стратегии игроков.
Задача на анализ информации, представленной в виде графа, является одной из предлагаемых на государственной итоговой аттестации по информатике.
Итак, сегодня вы узнали о том, какие бывают графы и из каких элементов они состоят, для каких целей создаются. Получили представление об ориентированных и неориентированных графах, деревьях. Научились решать задачи на определение количества путей в графе, используемые при государственной итоговой аттестации. Закрепите полученные знания на практике, выполнив упражнения.
Вводятся понятия — Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Дерево. Корень, лист, вершина.
2. Определяется необходимость рассмотрения группы объектов вместе с существующими между ними связями, т.е. системы. Затем — возможность получения информационной модели системы в форме графа. Рассматриваются различные варианты отображения графов;
3. Определение понятий — Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Дерево. Корень, лист, вершина.
4. Исследование различных возможных путей, проходящих по вершинам и ребрам графа. Цепь. Цикл.
5. Реализация интерактивного элемента с целью проверки первичного усвоения нового материала;
6. Определение сети. Исследование возможных вариантов применения информационных моделей в форме графов в повседневной жизни;
7. Определение Дерева. Корень, Предки, Потомки, Листья. Исследование возможностей, предоставляемых различными сервисами для построения генеалогического дерева;
8. Использование графов для графического представления решения различных задач. Задача о построении дерева возможных трёхзначных чисел.
Разбор задачи демонстрационного варианта ФИПИ-2017 на анализ информации, представленной в виде схем
Данный урок является 6-м в теме "Множества" по УМК Горячева и др. Включает презентацию и технологическую карту. Презентация может быть адаптирована для использования интерактивной доски. На уроке учащиеся знакомятся с понятием "граф", "элементы графа".
Технологическая карта урока
Граф Вершины и ребра графа
Планируемый результат обучения, в том числе и формирование УУД
Познавательные УУД: формировать умения выделять отношения, связывающие объекты.
Регулятивные УУД: формировать умение планирования, контроля, коррекции своих действий и оценки успешности усвоения .
Коммуникативные УУД: формировать умение аргументировать свое предложение, убеждать и уступать; формировать умение договариваться, находить общее решение; развивать внимание, способность к рассуждению, математическую речь.
Личностные УУД: развивать эмпатию и сопереживания, эмоционально-нравственную отзывчивость на основе развития способности к восприятию чувств других людей и экспрессию эмоций.
Основные понятия
Граф, вершина графа, ребро графа
Межпредметные связи
Математика, окружающий мир
Информатика в играх и задачах. 3 класс: Методические рекомендации для учителя. – авт.-сост. А. В.. Горячев, К. И. Горина. - М.: Баласс, 2009. – 128 с.
Информатика в играх и задачах. 3-й класс. Учебник в 2-х частях, часть 1 – 56 с. М.:Баласс, 2010.
ПК учителя, проектор, интерактивная доска
Рабочее место ученика
Этапы урока
Формируемые
Деятельность учителя
Деятельность учащегося
Долгожданный дан звонок, начинается урок.
Проверка домашнего задания
Регулятивные, коммуникативные УУД
Вопросы к обучающимся:
Какие у вас оказались в пересечении множеств дней, когда зебра каталась на лодке и когда зебра играла в футбол?
Какие дни вошли в круг?
Какие дни вы отметили в трапеции?
В какую фигуру вы вписали остальные дни? Почему?
Покажите друг другу, какую область вы закрасили желтым цветом.
Четверг и воскресенье
Среда и суббота вошли в общий квадрат, так как в эти дни зебра не развлекалась
Целеполагание и мотивация
Ребята, сегодня к нам на урок пришел лесной человечек.
Он обратился к нам с просьбой.
Дело в том, что ему нужно пройти через волшебную страну. В этом может помочь карта. Но карта это непростая, она невидимая и открывает свои секреты только тем, кто сможет сам нарисовать путь. Помните, что дорога через волшебную страну только одна и нельзя с нее сворачивать!
Актуализация знаний
Я прочитаю вам путь, а вы соедините объекты, которые в нем указаны:
Путь через волшебную страну начинается от высокой яблони.
Сначала нужно идти к древнему болоту и попросить у водяного пропуск через мостик. Дойти до моста, перейти его. Хочешь или нет, а придется идти в гости к Бабе-Яге, к избушке на курьих ножках. Даст Баба-Яга мешок зерна, это зерно нужно отнести не мельницу, смолоть. Потом взять муку и отдать ее мышке, что живет в корнях одинокой сосны. От сосны нужно идти в волшебный лес, передать привет мышкиной сестре, а она скажет заветные слова. Потом дойти до темной пещеры и сказать заветные слова. Тут и откроется выход!
Читайте также: