Граф с направленными рёбрами

Ребята, а вы помните сказку Алексея Николаевича Толстого «Золотой ключик, или Приключения Буратино»?

Вырезанный из полена мальчик Буратино знакомится с куклами театра злого Карабаса Барабаса: Мальвиной, Артемоном, Пьеро, Арлекином.

Чтобы освободить друзей, ему предстоит разгадать тайну золотого ключика. Буратино очень любит приключения.

А ещё, как оказалось, он очень любит рисовать и хочет нам показать свой рисунок.

̶ Посмотрите, как я умею рисовать!

̶ А что это за рисунок такой, Буратино?

̶ А чтобы узнать, что я здесь нарисовал, вам надо соединить все точки по порядку.

̶ Очень интересно, что же нарисовал Буратино. Будем соединять.

Конечно, начинаем с точки под номером один, которую соединим с точкой под номером два. Точку под номером два – с точкой под номером три и т.д. Посмотрите! Получился монитор!

А что же мы делали? Мы строили граф.

Давайте вспомним, что такое граф?

Граф – это множество точек, которые могут соединяться линиями.

Точки называются вершинами графа.

А линии, которые связывают вершины, называются рёбрами графа.

И сегодня на уроке мы будем продолжать учиться строить графы.

И в этом нам будут помогать герои сказки «Золотой ключик, или Приключения Буратино».

Посмотрите, что делают герои этой сказки?

Играют. Пьеро бросает мяч Мальвине, Мальвина – Буратино, Буратино - Арлекину, Арлекин ̶ Артемону, Артемон – Пьеро.

А теперь попросим Буратино и Мальвину отобразить графом их игру.

Ну, давайте посмотрим, как справились с этим заданием наши герои?

Итак! Вершины на двух графах одинаковые – это участники игры, а вот рёбра разные. Давайте разбираться, почему.

Чем отличаются рёбра у графов? На одном графе рёбра со стрелками, а на другом без стрелок. А давайте на мгновение вернёмся в начало нашего урока и вспомним тему: граф с направленными рёбрами. Это рёбра, у которых есть определённое направление (т.е. указано направление).

Посмотрим фрагмент игры. Именно Пьеро бросает мяч Мальвине, а не она ему, значит, ребро будет направлено от Пьеро к Мальвине.

Мальвина бросает мяч Буратино, ребро будет направлено от Мальвины к Буратино. Значит, Мальвина построила граф правильно. А Буратино следует ещё немного эту тему подучить.

Итак, направленные рёбра графа используются, если связь между объектами имеет направление. Например, если граф отображает отношение «отправил письмо», то стрелка направлена от отправителя к адресату, то есть к тому, кто его получит.

̶ Я понял свою ошибку, ̶  говорит Буратино. А ещё у меня есть идея. Давайте вырастим дерево «Животные» с помощью графа.

Хорошая идея, Буратино.

Итак.

От вершины «животные» одно ребро направлено к вершине «птицы», а другое – к вершине «звери».

Далее от вершины «птицы» рёбра направлены к вершинам «домашние» и «дикие». И от вершины «звери» направлены рёбра к таким же вершинам.

Затем от каждой вершины «домашние» рёбра направлены к двум вершинам «водоплавающие» и «не водоплавающие». И от вершин «дикие» направлены рёбра к таким же вершинам.

Какое красивое и большое дерево получилось.

̶ Гав! – согласен Артемон.

Ой, смотрите у него в зубах свёрток.

Давайте, прочитаем, что же там написано.

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

Ну, что ж попробуем. Рисуем вершины нашего графа. Вершинами будут все герои и не забываем называть каждую вершину, будем использовать заглавные буквы имени героев, а для пчёлки имя ПЧ, т.к. Пятачок тоже начинается на букву П.

Теперь проводим рёбра. Пятачок дружит с Кроликом, и Кролик дружит с Пятачком. Значит, ребро будет направленное со стрелками на обоих концах.

Также Пятачок дружит и с Совой и С Осликом. И они с ним дружат – опять рёбра имеют направления в обе стороны. Кролик дружит с Совой и Осликом и они дружат с Кроликом.

Сова и Ослик так же дружат друг с другом. Осталось связать дружбу Ослика и пчёлки. Граф дружбы построен.

А вам он ничего не напоминает? А так, а так? Конечно, у нас получился воздушный змей.

А только представьте себе, если вдруг Кролик поссорится с Пятачком и Совой… И воздушного змея у нас не будет. Но будем надеяться, что дружба у них крепкая и никто не с кем никогда не будет ссориться.

Вы представляете, нам пришло приглашение принять участие в конкурсе рисунков «Разукрась-ка». Но, конкурс необычный.

Необходимо прочитать описание и раскрасить цветик семицветик. Ну, что, попробуем! Главное, в этом деле не спешить и быть очень внимательными. И тогда мы точно займём первое место. А участников в этом конкурсе не мало.

Итак.

В серединке цветка находится нектар, он жёлтого цвета. Закрашиваем серединку цветка жёлтым цветом.

На красном лепестке сидели три пчёлки. Две пчёлки из трёх полетели к середине цветка за нектаром две пчёлки из трёх. Ищем этот лепесток и закрашиваем его красным цветом.

С розового лепестка полетела за нектаром только одна пчёлка из трёх. Где он? Ага, вот. Закрашиваем.

С голубого лепестка не полетела ни одна пчёлка. Нашли. На фиолетовом лепестке нет ни одной пчёлки. С лепестка зелёного цвета за нектаром отправились все пчёлки. На оранжевый лепесток из центра вернулась одна пчёлка. С бежевого лепестка одна пчёлка полетела за нектаром, а вторая уже вернулась назад. Все лепестки закрашены.

Какой красивый цветик семицветик у нас получился.

И конечно, наш рисунок займёт первое место!

Мы сегодня молодцы! Вместе с Буратино вырастили дерево из графа, выполнили задание, которое нам принёс Артемон, поучаствовали в конкурсе «Разукрась-ка» и теперь мы можем вспомнить, какие знания по теме «Граф» нам подарили сказочные герои.

Граф – это множество точек, которые могут соединяться линиями. Линия указывает на связь между двумя точками.

Точки называются вершинами графа.

А линии, которые связывают вершины, называются рёбрами графа.

Ребро, у которого есть стрелочка, указывающая направление, называется направленным.

Направленные рёбра графа используются, если связь между объектами имеет направление, как в случае отправитель и адресат письма.

Постарайтесь это запомнить.

А я хочу пожелать, чтобы у вас было такое же настроение, как выглядит наш цветик семицветик, весёлое и радужное.