XIV Международная студенческая научная конференция Студенческий научный форум - 2022

В настоящее время применение теории графов на уроках информатики в школе является актуальным. В Федеральном государственном образовательном стандарте представлены требования к результатам освоения основной образовательной программы, среди которых можно выделить: умение создавать, применять и преобразовывать знаки и символы, модели и схемы для решения учебных и познавательных задач; сформированность представлений о важнейших видах дискретных объектов и об их простейших свойствах, алгоритмах анализа этих объектов; умение строить математические объекты информатики. Данные навыки формируются непосредственно при изучении и использовании в решении задач теории графов. Кроме этого, задачи, для решения которых требуется применение графов, встречаются в заданиях ОГЭ и ЕГЭ по информатике, поэтому их изучение – важнейшая часть образовательного процесса.

Цель исследования – теоретическое обоснование применения занимательных задач теории графов в школьном курсе информатики.

Задачи, связанные с теорией графов, были рассмотрены ещё Л. Эйлером, однако впервые сам термин «граф» ввёл венгерский учёный Д. Кёнинг в 1936 году. Графом называют схемы, которые состоят из точек и отрезков (прямых или кривых), соединяющих эти точки. Точки называются вершинами графов, а отрезки – рёбрами графов.

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

Нулевой граф – граф, состоящий из изолированных вершин, то есть вершины в нём не соединены рёбрами.

Неполный граф – граф, в котором построены не все возможные рёбра.

Полный граф – граф, в котором построены все возможные рёбра. Для определения количества рёбер в таком графе используется формула: n(n – 1)/2, где n – число вершин в графе.

Ориентированный граф – граф, содержащий рёбра, для которых одна вершина является начальной, а другая – конечной.

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

Смежные вершины – вершины, соединённые ребром.

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

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

Цикл в графе – путь, в котором начало и конец совпадают.

Связные вершины – вершины, с концами в которых в графе существует путь. Граф, содержащий такие вершины, называется связным.

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

Задачи на применение теории графов в школьном курсе информатики встречаются уже в начальной школе. Так, например, в учебниках информатики УМК «Школа 2100», авторами которых являются Горячев А. В., Горина К. И. и Волкова Т. О., можно увидеть следующие задания:

1. При встрече Филя, Хрюша, Каркуша и Степашка поздоровались друг с другом. Сколько всего было рукопожатий?

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

2. Пять веселых человечков решили сыграть в шашки. Сколько всего партий будет сыграно, если каждый с каждым должен сыграть по одному разу?

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

3. Сколько всего дорожек? (рис. 1)

Рисунок 1 – Задание 37

Для решения задачи нужно посчитать количество дорог. Это можно сделать вручную, просто посчитав каждое ребро. Однако это полный граф, то есть все вершины соединены между собой рёбрами, поэтому посчитать можно по формуле n(n – 1)/2, где n – число вершин, т.е. число домиков. Получается 10 дорожек.

4. Шесть футбольных команд А, Б, В, Г, Д и Е должны сыграть матчи каждая с каждой. Уже сыграли матчи:

А с В, Г, Е

Б с В, Д, Е

В с А, Б

Г с А, Д, Е

Д с Б, Г, Е

Е с А, Б, Г, Д

Сколько матчей сыграно и сколько осталось сыграть?

Эта задача помечена звёздочкой, так как её решение более сложное, по сравнению с прошлыми заданиями. Здесь также нужно построить граф, но он будет неполным, поэтому необходимо строить только те рёбра, которые заданы в условии задачи, и посчитать их. Затем нужно определить то количество рёбер, которое бы если бы граф был полный, и вычесть из него имеющиеся рёбра. Тогда мы получим количество матчей, которое осталось сыграть. Это можно посчитать по формуле, а можно нарисовать рёбра несыгранных партий другим цветом и посчитать вручную. Для начальной школы предпочтительнее второй вариант. В результате построения графа получаем, что уже сыграно 9 партий и осталось сыграть 6 партий.

В начальной школе понятие графа, вершин и рёбер вводится уже в 3 классе, что служит отличной базой для изучения теории графов в старших классах, а также для сдачи ОГЭ и ЕГЭ по информатике.

В основной школе понятие графа встречается в учебнике информатики Л. Л. Босовой, А. Ю. Босовой для 6 класса в теме «Схемы». Именно здесь вводится понятие ориентированного и взвешенного графа, пути, цикла, дерева. Для решения с помощью теории графов предлагаются следующие задачи:

1. Сколькими способами можно рассадить в ряд на три стула трёх учеников? Выписать все возможные случаи.

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

Рисунок 2 – Граф к задаче 1

Далее выписываем все пути от вершин первого уровня к вершинам последнего (третьего) уровня: АВС, АСВ, ВАС, ВСА, САВ, СВА. Каждый путь – вариант рассадки учеников на стулья. Таким образом, получается 6 способов.

2. Чтобы привести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трёх дорог старого ворона и вот какие советы от него услышал:

1) иди сейчас по правой тропинке;

2) на следующей развилке не выбирай правую тропинку;

3) на третьей развилке не ходи по левой тропинке.

Пролетавший мимо голубь шепнул Ивану-царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?

Для решения этой задачи нужно построить граф-дерево. Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Подсказки ворона отметим более «жирными» рёбрами. Так как только один совет ворона верный, на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро, обозначим его дополнительной пунктирной линией. В итоге получим следующий граф (рис. 3):

Рисунок 3 – Граф-дерево к задаче 2

В 7 и 8 классах теория графов не упоминается и встречается уже только в 9 классе. Здесь ещё раз повторяются введённые в 6 классе понятия. Для решения предлагается следующая задача:

На берегу реки стоит крестьянин (К) с лодкой, а рядом с ним – собака (С), лиса (Л) и гусь (Г). Крестьянин должен переправиться сам и перевезти собаку, лису и гуся на другой берег. Однако в лодку кроме крестьянина помещается либо только собака, либо только лиса, либо только гусь. Оставлять же собаку с лисой или лису с гусём без присмотра крестьянина нельзя – собака представляет опасность для лисы, а лиса – для гуся. Как крестьянин должен организовать переправу?

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

Рисунок 4 – Граф-дерево переправы к задаче

На графе видно, что существуют два способа переправы через реку. Приведём план одного из них:

Крестьянин перевозит лису;

Крестьянин возвращается;

Крестьянин перевозит собаку;

Крестьянин возвращается с лисой;

Крестьянин перевозит гуся;

Крестьянин возвращается

Крестьянин перевозит лису.

Задачи, для решения которых можно использовать теорию графов, встречаются и в заданиях для ОГЭ и ЕГЭ. В вариантах ОГЭ согласно демоверсии 2022 года это задания 2, 4, 5, 9. В вариантах ЕГЭ – 1, 4, 13, 19, 23.

Рассмотрим некоторые из них:

Задание 4, ОГЭ.

Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых (в километрах) приведена в таблице. Передвигаться можно только по дорогам, указанным в таблице. Определите длину кратчайшего пути между пунктами A и F.

Рисунок 5 – Задание 4, ОГЭ

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

Рисунок 6 – Граф к заданию 4, ОГЭ

В результате получилось 5 дорог, посчитаем длину каждой из них.

AF = 15;

ACDEF = 5+1+2+1=9;

ABDEF = 3+4+2+1=10;

ACDF = 5+1+6=12;

ABDF = 3+4+6=13. Таким образом, длина кратчайшего пути равна 9.

Задание 13, ЕГЭ.

На рисунке представлена схема дорог, связывающих города А, F, G, В, E, C, D. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Д?

Рисунок 7 – Задание 13, ЕГЭ

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

Рисунок 8 – Граф-дерево к заданию 13, ЕГЭ

В результате получим 5 путей.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Аллёнов, С. В. Основы теории графов: методические рекомендации по изучению раздела «Теория графов» / С. В. Аллёнов. – Коломна: КГПИ, 2007. – 32 с.

2. Березина, А. Ю. Графы и их применение / А. Ю. Березина. – Москва: Просвещение, 1979. – 143 с.

3. Босова, Л. Л. Информатика и ИКТ : учебник для 9 класса / Л. Л. Босова. – Москва : БИНОМ. Лаборатория знаний, 2012. – 244 с.

4. Мельников, О. И. Занимательные задачи по теории графов / О. И. Мельников. – Минск: ТетраСистемс, 2001. – 144 с. 

Код для цитирования: Скопировать