Граф с направленными рёбрами
Урок 17. Информатика 3 класс
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Граф с направленными рёбрами»
Ребята, а вы помните сказку Алексея Николаевича Толстого «Золотой ключик, или Приключения Буратино»?
Вырезанный из полена мальчик Буратино знакомится с куклами театра злого Карабаса Барабаса: Мальвиной, Артемоном, Пьеро, Арлекином.
Чтобы освободить друзей, ему предстоит разгадать тайну золотого ключика. Буратино очень любит приключения.
А ещё, как оказалось, он очень любит рисовать и хочет нам показать свой рисунок.
̶ Посмотрите, как я умею рисовать!
̶ А что это за рисунок такой, Буратино?
̶ А чтобы узнать, что я здесь нарисовал, вам надо соединить все точки по порядку.
̶ Очень интересно, что же нарисовал Буратино. Будем соединять.
Конечно, начинаем с точки под номером один, которую соединим с точкой под номером два. Точку под номером два – с точкой под номером три и т.д. Посмотрите! Получился монитор!
А что же мы делали? Мы строили граф.
Давайте вспомним, что такое граф?
Граф – это множество точек, которые могут соединяться линиями.
Точки называются вершинами графа.
А линии, которые связывают вершины, называются рёбрами графа.
И сегодня на уроке мы будем продолжать учиться строить графы.
И в этом нам будут помогать герои сказки «Золотой ключик, или Приключения Буратино».
Посмотрите, что делают герои этой сказки?
А теперь попросим Буратино и Мальвину отобразить графом их игру.
Ну, давайте посмотрим, как справились с этим заданием наши герои?
Итак! Вершины на двух графах одинаковые – это участники игры, а вот рёбра разные. Давайте разбираться, почему.
Чем отличаются рёбра у графов? На одном графе рёбра со стрелками, а на другом без стрелок. А давайте на мгновение вернёмся в начало нашего урока и вспомним тему: граф с направленными рёбрами. Это рёбра, у которых есть определённое направление (т.е. указано направление).
Посмотрим фрагмент игры. Именно Пьеро бросает мяч Мальвине, а не она ему, значит, ребро будет направлено от Пьеро к Мальвине.
Мальвина бросает мяч Буратино, ребро будет направлено от Мальвины к Буратино. Значит, Мальвина построила граф правильно. А Буратино следует ещё немного эту тему подучить.
Итак, направленные рёбра графа используются, если связь между объектами имеет направление. Например, если граф отображает отношение «отправил письмо», то стрелка направлена от отправителя к адресату, то есть к тому, кто его получит.
̶ Я понял свою ошибку, ̶ говорит Буратино. А ещё у меня есть идея. Давайте вырастим дерево «Животные» с помощью графа.
Хорошая идея, Буратино.
От вершины «животные» одно ребро направлено к вершине «птицы», а другое – к вершине «звери».
Далее от вершины «птицы» рёбра направлены к вершинам «домашние» и «дикие». И от вершины «звери» направлены рёбра к таким же вершинам.
Затем от каждой вершины «домашние» рёбра направлены к двум вершинам «водоплавающие» и «не водоплавающие». И от вершин «дикие» направлены рёбра к таким же вершинам.
Какое красивое и большое дерево получилось.
̶ Гав! – согласен Артемон.
Ой, смотрите у него в зубах свёрток.
Давайте, прочитаем, что же там написано.
В одной прекрасной сказке жили замечательные герои: Пятачок, Кролик, Сова, Ослик. И все они дружили между собой. А Ослик ещё дружил с пчёлкой, которую никто не знал, кроме него. По данному описанию попробуйте построить граф дружбы. Будьте внимательны, не забудьте, что все герои, кроме пчёлки, дружат между собой, т.е. каждый с каждым.
Ну, что ж попробуем. Рисуем вершины нашего графа. Вершинами будут все герои и не забываем называть каждую вершину, будем использовать заглавные буквы имени героев, а для пчёлки имя ПЧ, т.к. Пятачок тоже начинается на букву П.
Теперь проводим рёбра. Пятачок дружит с Кроликом, и Кролик дружит с Пятачком. Значит, ребро будет направленное со стрелками на обоих концах.
Также Пятачок дружит и с Совой и С Осликом. И они с ним дружат – опять рёбра имеют направления в обе стороны. Кролик дружит с Совой и Осликом и они дружат с Кроликом.
Сова и Ослик так же дружат друг с другом. Осталось связать дружбу Ослика и пчёлки. Граф дружбы построен.
А вам он ничего не напоминает? А так, а так? Конечно, у нас получился воздушный змей.
А только представьте себе, если вдруг Кролик поссорится с Пятачком и Совой… И воздушного змея у нас не будет. Но будем надеяться, что дружба у них крепкая и никто не с кем никогда не будет ссориться.
Вы представляете, нам пришло приглашение принять участие в конкурсе рисунков «Разукрась-ка». Но, конкурс необычный.
Необходимо прочитать описание и раскрасить цветик семицветик. Ну, что, попробуем! Главное, в этом деле не спешить и быть очень внимательными. И тогда мы точно займём первое место. А участников в этом конкурсе не мало.
В серединке цветка находится нектар, он жёлтого цвета. Закрашиваем серединку цветка жёлтым цветом.
На красном лепестке сидели три пчёлки. Две пчёлки из трёх полетели к середине цветка за нектаром две пчёлки из трёх. Ищем этот лепесток и закрашиваем его красным цветом.
С розового лепестка полетела за нектаром только одна пчёлка из трёх. Где он? Ага, вот. Закрашиваем.
С голубого лепестка не полетела ни одна пчёлка. Нашли. На фиолетовом лепестке нет ни одной пчёлки. С лепестка зелёного цвета за нектаром отправились все пчёлки. На оранжевый лепесток из центра вернулась одна пчёлка. С бежевого лепестка одна пчёлка полетела за нектаром, а вторая уже вернулась назад. Все лепестки закрашены.
Какой красивый цветик семицветик у нас получился.
И конечно, наш рисунок займёт первое место!
Мы сегодня молодцы! Вместе с Буратино вырастили дерево из графа, выполнили задание, которое нам принёс Артемон, поучаствовали в конкурсе «Разукрась-ка» и теперь мы можем вспомнить, какие знания по теме «Граф» нам подарили сказочные герои.
Граф – это множество точек, которые могут соединяться линиями. Линия указывает на связь между двумя точками.
Точки называются вершинами графа.
А линии, которые связывают вершины, называются рёбрами графа.
Ребро, у которого есть стрелочка, указывающая направление, называется направленным.
Направленные рёбра графа используются, если связь между объектами имеет направление, как в случае отправитель и адресат письма.
Постарайтесь это запомнить.
А я хочу пожелать, чтобы у вас было такое же настроение, как выглядит наш цветик семицветик, весёлое и радужное.
Графы: основы теории, алгоритмы поиска
Возможно, вы уже знакомы с понятием спортивного программирования и знаете, что оно помогает развить навыки решения проблем и прокачать технические знания о структурах данных и алгоритмах.
Одной из важнейших составляющих спортивного программирования является изучение алгоритмов. В этой статье мы охватим большое количество алгоритмов, в том числе все алгоритмы на графах, знание которых понадобится вам для успешного решения задач из теории графов на соревнованиях по программированию. Конечно, одних теоретических знаний алгоритмов недостаточно, и вам придётся набить руку в решении практических задач на таких сайтах, как Codeforces. Настоящая же статья представит вам инструменты, необходимые для освоения важных графовых алгоритмов. Итак, приступим.
Что такое граф?
Графы, в понимании программистов, — это не те графики, которые мы изучали в школе. Это не столбиковые диаграммы или гистограммы.
С точки зрения компьютерных наук и дискретной математики, графы — это абстрактный способ представления типов отношений, например дорог, соединяющих города, и других видов сетей. Графы состоят из рёбер и вершин. Вершина — это точка на графе, а ребро — это то, что соединяет две точки на графе.
Пример графа
В условиях задач из теории графов на соревнованиях по программированию обычно говорится о таких вещах, как сети и решётки.
Вот список всех терминов, относящихся к теории графов, которые вам нужно знать:
Представление графов в коде
Для того, чтобы использовать алгоритмы на графах в коде, сначала нам нужно разобраться, как осуществляется представление графов в коде. Весь следующий код будет на C++, так как для спортивного программирования я предпочитаю именно этот язык за его скорость и встроенные функции, позволяющие упростить написание решений задач.
Будут показаны два способа представления графов: матрицы смежности и списки смежности. Больше вам пригодится представление графов в виде списка смежности.
Матрицы смежности
Матрица смежности представляет собой граф в виде двумерной матрицы с размерами V x V, где V — количество вершин графа. Матрицы смежности лучше всего применять, когда V² примерно равно E (числу рёбер), то есть когда граф плотный. Запись a_ij обозначает, сколько рёбер соединяют вершину i и вершину j.
Списки смежности
Другой распространенный способ представления графов в коде — списки смежности. Суть в том, что вы создаёте списки соседей для каждой вершины, а затем помещаете все эти списки в другой список. Их лучше всего применять, когда в графе небольшое количество рёбер, то есть когда граф разрежённый. Если у вас взвешенный граф, т.е. каждое ребро графа имеет какой-то вес, то в списке будут содержаться пары для рёбер (сосед, вес).
Поиск в глубину
Теперь, когда мы научились представлять графы в коде, можем приступить к изучению некоторых алгоритмов на графах! Начнём с поиска в глубину (DFS) и завершим поиском в ширину (BFS). Чтобы не загромождать статью, алгоритмы поиска пути не будут здесь рассматриваться (интересующиеся могут ознакомиться с алгоритмом поиска кратчайшего пути Беллмана-Форда).
Поиск в глубину — это один из базовых алгоритмов на графах. Он применяется для поиска расстояния от одной вершины до других вершин в графе. Это алгоритм обхода.
Поиск в глубину помечает каждую вершину в графе одной из двух меток: посещённая или не посещённая. Алгоритм помечает каждую вершину как посещённую, если удаётся избежать циклов. Он работает следующим образом:
Поиск в ширину
Поиск в ширину — ещё один алгоритм обхода графов. Вместе с алгоритмом поиска вглубь он составит большую часть увлекательных соревнований по программированию, по крайней мере, тех из них, что относятся к графам.
Поиск в ширину тоже помещает каждую вершину в графе в одну из двух категорий: посещённых или непосещённых. И цель у обоих алгоритмов одна и та же: помечать каждую вершину в графе как посещённую, если удаётся избежать циклов. Вот как работает алгоритм поиска в ширину:
Как видите, алгоритм поиска в ширину очень похож на алгоритм поиска в глубину. Однако вместо того, чтобы спускаться вниз по ветви графа или дерева, как это делает алгоритм поиска в глубину, алгоритм поиска в ширину проходит каждый уровень.
Заключение
Освоив теоретическую часть, касающуюся двух самых важных алгоритмов обхода на графах, вам остаётся только практиковаться, чтобы использовать эти алгоритмы в соревнованиях по программированию. Я бы порекомендовал для начала Codeforces: решайте задачи, помеченные тегами bfs и dfs с рейтингом до 1400. Когда почувствуете, что справляетесь с ними, увеличьте сложность.
Отработка навыков решения алгоритмических задач, особенно алгоритмов на графах, поможет вам побеждать на соревнованиях по программированию и успешно проходить технические собеседования. Вперёд — к успехам!
Урок информатики в 3 классе. Графы.Вершины и рёбра графа.
Онлайн-конференция
«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»
Свидетельство и скидка на обучение каждому участнику
Урок информатики. 3 класс.
Тема. Графы. Вершины и рёбра графа.
познакомить учащихся с понятием “граф”, основными принципами его построения;
формировать умение выделять отношения, связывающие объекты;
развивать внимание, способность к рассуждению, математическую речь;
воспитывать взаимопомощь, умение работать в коллективе.
Организационный момент. Разминка.
Царица наук – математика.
Но выросла рядом принцесса –
Дочь мысли людской и прогресса.
Сегодня без этой науки
Представить наш мир невозможно.
Она нас спасает от скуки.
Она наш помощник надежный.
Мы начинаем наш урок и отправляемся за новыми знаниями. Проверим, всё ли у нас на месте: карандаши, ручки, тетради, листы с заданиями. Сначала проведём разминку.
На осине созрело 5 яблок, а на липе – 10. Сколько всего яблок созрело на этих деревьях? ( Нисколько)
Серёжа тратит на дорогу в школу 5 минут. Сколько минут он истратит, если пойдёт в школу вдвоём с братом? (Столько же).
Двое друзей играли в шахматы 2 часа. Сколько времени играл каждый из них? ( 2 часа)
Может ли щука назвать себя рыбой? (Нет, она не умеет разговаривать)
Какие дни у вас оказались в пересечении множеств дней, когда зебра каталась на лодке и когда зебра играла в футбол? (Четверг и воскресенье.)
Какие дни вошли в круг? (Вторник, пятница.)
Какие дни вы отметили в трапеции? (Понедельник, четверг.)
В какую фигуру вы вписали остальные дни? Почему? (Среда и суббота вошли в общий квадрат, так как в эти дни зебра не развлекалась.)
Покажите друг другу, какую область вы закрасили желтым цветом.
Покажи «светофором», как ты справился с заданием?
Актуализация знаний. Определение темы и задач урока.
Чтобы определить тему нашего урока, предлагаю вам выполнить несколько заданий. 
Какое слово здесь «спрятано»? (Граф)
Что оно означает? (Ответы детей)
объект, состоящий из вершин и соединяющих их рёбер.
Попробуйте решить логическую задачу
(создание проблемной ситуации).
В одном дворе жили мальчики: Вася, Коля, Петя, Олег. Вася дружит с Колей. Коля дружит с Петей. Петя дружит с Васей. Вася дружит с Олегом. Сколько друзей у Васи? У Пети?
(Учащимся предлагается решить задачу, но условие в первом случае представлено в текстовой форме, а во втором – в графическом. )
Вася дружит с Колей.
Коля дружит с Петей.
Петя дружит с Васей.
Вася дружит с Олегом.
Какой способ записи условия задачи удобнее использовать для того, чтобы быстро решить задачу?
А теперь вам предстоит разгадать два ребуса. Слайд.
Что означают эти понятия? (Ответы детей)
Вершины – точки, обозначающие объекты, которые связаны между собой. Обычно вершины не располагают на одной линии, а точки ставятся произвольно.
Рёбра графа – это линии, которые связывают вершины. Они обозначают связь между объектами.
Следовательно, ГРАФ – это объект, состоящий из вершин и соединяющих их рёбер.
Это тема нашего урока. Чем мы будем заниматься на уроке? (строить графы, обозначать вершины и рёбра).
Работа с новым материалом.
Одним из самых красивых графов являются созвездия.
Выбери любые два из предложенных созвездий. Изобрази созвездие в виде графа. Посчитай количество вершин и рёбер.
Сейчас мы с вами отправимся в путешествие по сладким странам. Рассмотрите внимательно картинку ( задание №27 )
Сколько стран на «сладкой карте»? (4)
Как они называются? («Зефирия», «Конфетия», «Шоколандия», «Вафландия»)
Сколько дорог на карте?(4)
Как вы думаете, сколько всего вершин (точек) должно быть у правильного графа дорог? (4) Сколько рёбер (линий) должно у него быть? (4)
Проверка – Слайд (тригер)
на 1-м графе есть ребро 3-Ш, а на карте такой дороги нет;
на 2-м графе 5 рёбер, а должно быть 4.
На какие из этих вопросов можно ответить, глядя на граф, а не на карту:
Сколько километров от Зефирии до Конфетии? (Нельзя ответить.)
Сколько дорог на карте? (Столько, сколько рёбер
Какая страна расположена южнее: Вафландия или Зефирия? (Нельзя ответить.)
Построена ли дорога из Шоколандии в Зефирию или нужно добираться проездом через другую страну? (Такой дороги нет, добираться нужно через Конфетию или через Вафландию и Конфетию.)
Гимнастика для глаз.
Глазки у ребят устали. (Поморгать глазами)
Ах, как солнце высоко. (Посмотреть вверх.)
Мы глаза сейчас закроем, (Закрыть глаза ладошками)
В классе радугу построим,
Вправо, влево повернем
В одной из сладких стран живут весёлые и дружные зайчата. Но однажды с ними приключилась неприятная история.
Рассмотрите граф к первому предложению. Что значит: “зайчата жили дружно”. Бегун дружил со всеми, Грызун дружил со всеми и т. д.
Рассмотрите граф. Что в данном графе обозначают вершины? (Зайчат.) Ребра? (Дружбу.)
Прочитаем второе предложение. Кто поссорился? Это значит, что их отношения прекратились. Чем второй граф будет отличаться от первого? (Не будет ребра П-Г.)
Прочитаем третье предложение. Как теперь изменился граф? (Не будет ребра И-Б.)
Сколько ребер у третьего графа?
Прочитайте последнее предложение. Мама помирила зайчат, значит, они снова все дружат.
Покажите, с кем дружит Прыгун.
С кем дружит Игрун? Покажите это па графе.
Какой зайчик остался? Отметьте на графе, с кем он дружит.
Составление алгоритма построения графа.
Mp3 (песенка Винни-Пуха)
Мы знаем, Винни-Пух очень любит ходить в гости. Вини-Пух вышел рано утром из дома, зашёл в гости к Сове, потом к Кролику. Затем зашёл в лес собрал грибов, около озера поговорил с Осликом Иа, а потом зашёл в гости к Пятачку.
Давайте построим граф, который будет отображать утренний маршрут Винни-Пуха. А для этого назовём шаги, которые нужно сделать, чтобы построить граф.
Определить и нарисовать вершины.
Давайте подумаем, какие объекты будут вершинами графа? Дом Винни-Пуха, Сова, Кролик, лес, Ослик Иа, Пятачок. Обратите внимание, что вершины обозначены заглавными буквами, и каждая вершина имеет своё обозначение.
А теперь надо соединить вершины так, чтобы рёбра графа отображали путь, по которому шёл Винни-Пух. Итак. Винни-Пух вышел из дома и зашёл в Сове, значит, соединяем эти две вершины. После Совы Винни-Пух зашёл к Кролику, соединяем вершины Сову и Кролика. Затем зашёл в лес, к Ослику Иа и к Пятачку. Граф построен, и весь путь Винни-Пуха отображён.
В мире новых технологий
В нём для нас секретов нет.
Слово «информатика» знакомо нынче всем.
Оно уже во все проникло сферы.
Решает информатика множество проблем,
Вы сами вспомнить можете примеры.
Приведите примеры, где в жизни мы можем встретить графы?
маршруты пути на карте;
отношения между объектами живой и неживой природы;
решение логических задач ( Приложение ЕКЦОР )
Курс повышения квалификации
Дистанционное обучение как современный формат преподавания
Курс профессиональной переподготовки
Информатика: теория и методика преподавания в образовательной организации
Курс повышения квалификации
Современные педтехнологии в деятельности учителя
Ищем педагогов в команду «Инфоурок»
Номер материала: ДБ-160583
Не нашли то что искали?
Вам будут интересны эти курсы:
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.
Школьники из Москвы выступят на Международной олимпиаде мегаполисов
Время чтения: 3 минуты
МГУ откроет первую в России магистерскую программу по биоэтике
Время чтения: 2 минуты
Путин поручил не считать выплаты за классное руководство в средней зарплате
Время чтения: 1 минута
В МГПУ сформулировали новые принципы повышения квалификации
Время чтения: 4 минуты
Учителям предлагают 1,5 миллиона рублей за переезд в Златоуст
Время чтения: 1 минута
ВПР для школьников в 2022 году пройдут весной
Время чтения: 1 минута
Подарочные сертификаты
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.
