Графы. От простого к сложному

Научно-практическая конференция школьников

«Первые шаги в науку 2013»

ГРАФЫ.

ОТ ПРОСТОГО К СЛОЖНОМУ.

Исследовательская работа по Информатике и ИКТ

Выполнили:

ученик 9 б класса

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

Научный руководитель:

, учитель Информатики и ИКТ.

Муниципальное бюджетное общеобразовательное учреждение

«Средняя общеобразовательная школа №4 г. Брянска

с углубленным изучением отдельных предметов»

Введение.

Довольно часто возникает ситуация, когда нам приходиться представлять различного рода данные в виде более мелких элементов входящих в состав системы.

Например, Русский язык. Части речи представленные в виде естественной классификации можно рассматривать в следующем графическом виде:

Данный вид расположения данных является графом. То есть, не замечая того, мы весьма часто сталкиваемся с применением теории графов в школе, сами того не осознавая.

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

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

В данной работе я хочу рассмотреть применение графов в предмете информатика и ИКТ переходя от более простых заданий рассматриваемых в 9 классе школьного курса к более сложным.

1. Что же такое граф?

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. [1]

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

Дуги данного графа обозначают связь «быть отцом»…

…У каждого человека может быть только один отец, но несколько детей. Поэтому в каждую вершину графа может входить только одна стрелка (дуга), а выходить — несколько. Такой граф представляет собой генеалогическое дерево.

Деревом называют граф, в котором нет петель, т. е. связанных по замкнутой линии вершин. [2]

Система, информационная модель которой представляется в виде дерева, называется иерархической системой…

…Для дерева выполняется правило: вершины верхнего уровня связаны с вершинами нижнего уровня как «один ко многим». Один континент содержит множество стран, одна страна — множество регионов, а не наоборот.

Иерархическими являются различные системы классификации в науке. Например, в биологии весь животный мир Земли рассматривается как система, которая делится на типы животных, типы делятся на классы, классы состоят из отрядов, отряды — из семейств, семейства делятся на роды, роды — на виды. Следовательно, система животных имеет шестиуровневую иерархическую структуру. [2]

По мимо этого есть графы где используется совсем другой принцип связи. Этот принцип – «многие ко многим». В учебнике 9 класса рассматривается граф посещения учениками различных факультативов. Он приведен на рисунке (смотри Приложение 1). Здесь один ученик может посещать множество факультативов, а один факультатив посещает множество учеников. Граф с такой структурой называют сеть. Здесь возможно произвольное соединение элементов графа, то есть каждый элемент может быть соединен с любым другим.

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

2. Применение графов к решению задач из ГИА за 9 класс

В Демо варианте ГИА приводятся следующие задания:

1) В части 1 № 3.

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

	А	В	С	D	E	F
A		3	5			15
B	3		3
C	5	3		5	2
D			5			3
E			2			7
F	15			3	7

Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам указанным в таблице.

115 [3]

Для решения задач данного типа были использованы материалы для подготовки к решению задач из ГИА и ЕГЭ с сайта К. Полякова.

Решение.

Путь следования лежит из пункта А. Смотрим в какие пункты мы можем попасть из А. Выносим их на схему и указываем длину пути.

А 3

15 5

F C В

Теперь аналогично рассмотрим пути, ведущие от пункта В.

А 3

15 5

F C В 3

2 С 5

Е D 3

7 F F

Аналогично рассмотрим ветку ведущую из пункта С. И подсчитаем длину всех путей.

А 3

15 5

F-15 2 C 5 В 3

7 E 3 D 2 С 5

F - 14 F - 13 Е D 3

7 F - 15 F -14

Итак, самый короткий путь 13. Это ответ №3

Ответ: 3

2) В части 2 №11

На рисунке – схема дорог, связывающая города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в К?

Б Д

А К

В

Г Е

Ответ: ______________________ [3]

Задание весьма напоминает предыдущее. Различие лишь в том, что данные даны в виде рисунка. И нам не надо искать длину пути.

Решение.

Строим граф. Начинаем с вершины А и проходим по всем веткам пути. В результате получаем следующий граф.

А

F B Б

Е В Е Д В Д

К Е Д К К Е Д К

К К К К

У нас получилось 8 путей, которыми мы можем доехать из города А в город К.

Ответ: 8

3) В части 2 №14

У исполнителя Квадратор две команды, которым присвоены номера:

1. возвести в квадрат

2.прибавить 1

Первая из них возводит число на экране во вторую степень, вторая – прибавляет к числу 1.

Составьте алгоритм получения из числа 1 числа 26, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 21221 – это алгоритм:

прибавить 1

возвести в квадрат

прибавить 1

прибавить 1

возвести в квадрат, который преобразует число 1 в 36)

Если таких алгоритмов более одного, то запишите один из них.

Ответ: __________________________ [3]

Решение.

Данное задание также решается с помощью графов.

Начинаем построение с 1, и рассматриваем два направления решения.

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

1

возведем в квадрат +1

1  2

возведем в квадрат +1

4 3

возведем в квадрат +1

16 5

возведем в квадрат +1

25 6

возведем в квадрат +1

625 26

Итак, рассматривая полученный граф получаем следующий путь 21212.

Ответ: 21212

3. Применение графов к решению задач ЕГЭ

По мимо рассмотренных нами задач, в варианте ЕГЭ добавляется еще одна задача на построение графа.

Задача Путешественник пришел в 08:00 на автостанцию поселка ЛЕСНОЕ и увидел следующее расписание автобусов:

Отправление из Прибытие в Время отправления Время прибытия

ЛЕСНОЕ ОЗЕРНОЕ 07:45 08:55

ЛУГОВОЕ ЛЕСНОЕ 08:00 09:10

ПОЛЕВОЕ ЛЕСНОЕ 08:55 11:25

ПОЛЕВОЕ ЛУГОВОЕ 09:10 10:10

ЛЕСНОЕ ПОЛЕВОЕ 09:15 11:45

ОЗЕРНОЕ ПОЛЕВОЕ 09:15 10:30

ЛЕСНОЕ ЛУГОВОЕ 09:20 10:30

ОЗЕРНОЕ ЛЕСНОЕ 09:25 10:35

ЛУГОВОЕ ПОЛЕВОЕ 10:40 11:40

ПОЛЕВОЕ ОЗЕРНОЕ 10:45 12:00

Определите самое раннее время, когда путешественник сможет оказаться в пункте ПОЛЕВОЕ согласно этому расписанию.

1) 10:30 2) 11:25 3)11:40 4) 11:45 [4]

Решение.

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

9:15 Лесное 7:45

11:45 9:20 8:55

Полевое Луговое 10:30 Озерное

10:40 9:15

Полевое 11:40 Полевое 10:30

По графу самое раннее время прибытия в Полевое выходит 10:30, но по условию задачи «путешественник пришел в Лесное в 8:00». Тогда данная ветка не является правильным решением. А решение будет время 11:30.

Ответ: 3

4. Кое-что интересное

В Современно задачнике по Турбо Паскалю разобран интересный пример.

Пример 45. Исполнитель умеет: умножать число на 2; увеличивать число на 1. Подсчитать число операций в самом коротком алгоритме получения данным исполнителем натурального числа n из единицы. (Программу выполненную на языке Паскаль смотрите в Приложении 2).

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

Двоичное дерево быстро растет, но заметим, что для обратного хода достаточно пяти действий. На каждом шагу выполняется одна из операций, обратных операциям исполнителя. Следовательно, искомая цепочка преобразований имеет вид: 1®2®4®5®10®11. Можно доказать, что в ней [log2n]+q-1 операций, где q – число единиц в двоичной записи числа n. Например, если n=2001, то операций 16, т. к. 20012 = (q=7), [log22001]+7-1=16 (квадратные скобки обозначают целую часть числа).[5]

Данный пример не показывает новых структур, однако алгоритм решения данной задачи стоит знать. Часто он применяется в известном алгоритме «быстрая степень». В более сложных задачах – операцию обратного хода нужно сначала увидеть. Для этого иногда приходиться применять дополнительные действия, или специальную подготовку.
ЗАКЛЮЧЕНИЕ.

Итак, мы рассмотрели три задачи, приведенные в Демо варианте ГИА. Эти задачи можно решать и другими способами. Но применение графов позволяет нам решать задачи таких типов более наглядно. Построив граф, мы сразу видим оптимальный путь решения. Графы позволяют ученикам меньше допускать ошибок. Они являются простым и эффективным средством для решения рассмотренных нами задач.

Рассмотренная задача из ЕГЭ является несколько более сложной. Вероятность ошибки в ней увеличивается за счет появления времени отправления и прибытия. За данными параметрами необходимо четко следить, так как их несоответствие ведет к появлению ошибок.

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

Используемые в тексте ссылки:

1.  Сайт Википедия – версия энциклопедии на русском языке (http://ru. wikipedia. org/wiki);

2.  , , 9 класс Информатика и ИКТ;

3.  Демо-вариант ГИА по информатике за 2013.

4.  Сайт Полякова (материалы для подготовки к ГИА и ЕГЭ)

(http://*****/school/ege. htm);

5.  Современный задачник по Турбо Паскалю.

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА.

Сайт Википедия – версия энциклопедии на русском языке (http://ru. wikipedia. org/wiki); , , 9 класс Информатика и ИКТ; Демо-вариант ГИА по информатике за 2013. Полякова (материалы для подготовки к ГИА и ЕГЭ)

(http://*****/school/ege. htm);

Современный задачник по Турбо Паскалю.

Приложение 1

 

Приложение 2

Const n:LongInt = 11; q:Byte = 0;

BEGIN

Write(n);

While n>1 do begin if Odd(n) then Dec(n) else n:=n div2; Inc(q);

Write(n); end;

Writeln; Write(‘Всего операций: ‘,q); Readln;

END.