XV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Применение графов к решению задач
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
1Введение
В своей работе я бы хотела изучить такой раздел математики как теория графов. Рассмотрим несколько математических и лексических задач и изучим, как изображение данных в виде графов упрощает их решение.
Основоположником теории графов считается известный математик Леонард Эйлер, в 1736 году решивший загадку о Кенигсбергских мостах, изобразив схему города в упрощенном виде – как мы бы сейчас сказали, построив граф. Однако термин «граф» впервые ввел в математику венгерский математик Денеш Кениг в 1936 году.
Что такое граф? Граф – это множество вершин (их еще называют узлами), соединенных ребрами. Каждое ребро всегда соединено ровно с двумя вершинами, или, как еще говорят, инцидентно им. Например, схема метро всегда изображается в виде графа, где узлами являются станции метро, а ребрами – перегоны, их соединяющие. И когда мы думаем, как добраться от одной станции до другой, мы, по сути, перебираем все возможные пути, их соединяющие. Путь – это последовательность узлов, такая что каждые два соседних узла соединены ребром. Граф называется связным, если для любых двух его вершин существует хотя бы один путь. Если путь начинается и заканчивается в одной и той же вершине, то он называется циклом.
Особенно меня заинтересовал такой вид графов, как деревья – связные графы, в которых нет циклов. Самый частый пример использования дерева в быту – генеалогическое дерево. Мы будем рассматривать корневые деревья – деревья, у которых одна из вершин называется корнем, а соединенные с ней ребрами другие вершины (их еще называют смежными) – ее потомками.
2Решение задачи по теории вероятностей
Рассмотрим построение графа на примере задачи по теории вероятностей, встречающейся в ЕГЭ.
|
На рисунке изображён лабиринт. Паук заползает в лабиринт в точке «Вход». Развернуться и ползти назад паук не может, поэтому на каждом разветвлении паук выбирает один из путей, по которому ещё не полз. Считая, что выбор дальнейшего пути чисто случайный, определите, с какой вероятностью паук придёт к выходу D. |
Построим по условию задачи дерево, в котором в узлы запишем текущее место нахождения паука либо сделанный выбор:
Наше дерево очень наглядно показывает, что для того, чтобы выйти через выход D, пауку нужно сделать правильный выбор на 4 развилках, в каждой из них он оказывается перед выбором из двух вариантов, то есть итоговая вероятность вычисляется по формуле 0,5*0,5*0,5*0,5=0,0625.
3Представление арифметического выражения в виде дерева
Изобразим теперь в виде дерева арифметический пример в несколько действий. Числа будут концевыми узлами (узлами, инцидентными только одному ребру), а их предками будут выступать выполняемые над этими числами операции сложения, вычитания, умножения, деления. Так как операции сложения и умножения обладают переместительным и сочетательным свойствами, то узлы + или * могут быть соединены ребрами более чем с двумя потомками, например, выражение 2+7+3 можно изобразить так:
Но операции вычитания и деления строго зависят от порядка чисел, поэтому такие узлы всегда будут иметь ровно два потомка и обходиться слева направо. Изобразим выражение 45:3:5
В первом примере наше дерево имело два уровня: корневой узел + с нулевым уровнем и три его потомка, каждый первого уровня. Уровнем узла называется длина пути, соединяющего этот узел с корневым. Во втором примере дерево уже имеет три уровня.
Построим дерево для более сложного примера:
В математике это называется дробным выражением, и черту дроби, отделяющую числитель этого выражения от знаменателя, мы заменим на деление:
Представив пример в таком виде, можно увидеть поддеревья – узлы исходного дерева, которые сами являются деревом. При работе с арифметическими и алгебраическими выражениями, если мы захотим рассмотреть поддерево, имеющее в качестве корневого какой-то узел, то мы будем обязаны включить в него всех потомков вплоть до концевых, но в следующем разделе этой работы мы рассмотрим другой, более распространенный способ нахождения поддеревьев.
Рассмотрим такие поддеревья:
Очевидно, что каждое из них является законченным выражением, значение которого мы используем для решения исходного примера.
4Семантические деревья
Рассмотрим теперь, как деревья могут нам помочь при решении не только математических, а, например, лексических задач.
Допустим, мы читаем текст и видим длинное предложение, в котором не всегда сразу понятно, какие слова к каким относятся. Если мы построим связи между этими словами при помощи вопросительных слов, то, по сути, мы построим ребра, соединяющие узлы – члены предложения. Любое предложение таким образом можно изобразить в виде графа, а если договориться, какой член предложения считать корневым узлом – то и в виде дерева.
Я рассмотрела разные варианты, чаще всего лингвисты используют в качестве корня сказуемое, но не всегда это получается удобным, например, если в предложении есть однородные сказуемые. Поэтому я решила считать корневым узлом подлежащее, а в тех случаях, когда подлежащее сложное: «мама с папой», «Саша и Маша» - считать его одной вершиной.
Построим дерево по предложению из рассказа Носова «Витя Малеев в школе и дома»:
-
Яркое солнышко сияло в небе по-летнему.
Мы можем интуитивно, а также на основе школьных знаний указать некоторые связи слов в этом предложении. Сразу же очевидны подлежащее «солнышко» и сказуемое «сияло». Слово «яркое» отвечает на вопрос «какое?» заданный подлежащему, а сочетания «в небе» и «по-летнему» уточняют сказуемое, отвечая на вопросы «где?» и «как?». Таким образом напрашивается следующая схема зависимостей:
Наш граф имеет пять узлов. Так как предложение простое, то в нем один корень. Случаи сложносочиненных и сложноподчиненных предложений рассмотрим дальше.
Какую информацию мы теперь можем получить? Например, выписать из предложения сочетания «связанных слов»:
Яркое солнышко
Солнышко сияло в небе
В итоге, мы выписали несколько поддеревьев исходного дерева! Как же выписать все возможные? Для этого нам нужен алгоритм упорядоченного обхода связанных узлов. Будем обходить исходное дерево слева направо, снизу вверх.
Рассмотрим отдельно по очереди каждую ветвь, идущую от корня. Если в ней больше одного узла, эту ветвь будем обходить снизу, от концевых вершин:
Яркое
В небе
По-летнему
Сияло
Сияло в небе
Сияло по-летнему
Сияло в небе по-летнему
Теперь включим корень. Так как поддерево – это связный граф, то мы не можем выписать сочетание «солнышко по-летнему», после корневого узла всегда будет идти смежный с ним узел:
Солнышко
Солнышко яркое
Солнышко сияло
Солнышко сияло в небе
Солнышко сияло по-летнему
Солнышко сияло в небе по-летнему
Солнышко яркое сияло
Солнышко яркое сияло в небе
Солнышко яркое сияло по-летнему
Солнышко яркое сияло в небе по –летнему
Мы выписали 17 поддеревьев. Конечно, появляется вопрос: можно ли подсчитать количество поддеревьев исходного дерева, не выписывая их все? Выведем формулу подсчета.
Рассмотрим снова наше дерево, для удобства обозначив узлы буквами:
Каждому узлу будем ставить в соответствие число, показывающее, сколько деревьев с собой в качестве корня он имеет.
Концевые узлы получают число 1, т.к. они не имеют потомков.
Наше дерево приобрело такой вид:
Рассмотрим теперь не концевой узел на уровень меньше максимального – это узел В. Подсчитаем, сколько поддеревьев он образует:
В
ВГ
ВД
ВГД
Заметим, что в данном случае у нас обязательно первой идет буква В, а к ней может либо присоединиться ветвь, либо нет. Из узла В выходят две ветви, каждую можно либо присоединять, либо нет. Получаем 2*2=4 варианта. На рисунке видим следующее:
Теперь найдем все поддеревья узла а:
А
АБ
АВ
АВГ
АВД
АВГД
АБВ
АБВГ
АБВД
АБВГД
Из узла А выходят две ветви, каждую из них либо включаем, либо нет. При этом ветвь Б можно включить ровно одним способом, а ветвь В – 4 способами. Итого всего (1+1)*(4+1)=10 вариантов.
Всего же возможных сочетаний 1+1+1+4+10=17.
Покажем работу формулы еще на одном примере:
Г=1, Д=1, Е=1, Б=(1+1)*(1+1)=4, В=1+1=2, А=(4+1)*(2+1)=15
1+1+1+4+2+15=24
Проверим, выписав все поддеревья:
Г, Д, Е, Б, БГ, БД, БГД, В, ВЕ, А, АБ, АБГ, АБД, АБГД, АВ, АВЕ, АБВ, АБВЕ, АБГВ, АБГВЕ, АБДВ, АБДВЕ, АБГДВ, АБГДВЕ – итого 24.
Рассмотрим теперь построение деревьев и подсчет количества сочетаний на примере сложных предложений.
|
Уже прозвонил звонок, и в класс пришла Ольга Николаевна. |
Сложносочиненное предложение, 2 корневых узла, всего 12 поддеревьев:
|
Целое лето я только и делал, что бегал по улицам да играл в футбол. |
Сложноподчиненное предложение, 1 корневой узел – подлежащее главного предложения, а подчиненное предложение зависит от слова бегал, 81 поддерево:
Понятно, что чем сложнее дерево (больше узлов и разветвлений), тем больше возможных поддеревьев можно составить. Если мы хотим строить их для большого количества предложений, удобно составить компьютерную программу и автоматизировать этот процесс.
Ниже приведен пример реализации алгоритма на языке программирования C#:
|
class TreeNode { // Свойство, перечисляющее потомков данного узла publicvirtual IEnumerable<TreeNode> Childs { get; set; } // Функция, вычисляющяя число поддеревьев, // в дереве с корнем в текущем узле public (int current, int global) CountSubtrees() { int c = 1, g = 0; // для всех потомков текущего узла foreach (var child in Childs) { // вычисляемчислоподдеревьев var r = child.CountSubtrees(); // составляем произведение c *= r.current + 1; // и одновременно аккумулируем результат g += r.global; } return (c, g + c); } } |
Для обработки текстов программой необходимо сначала вручную построить дерево для каждого предложения. Приведу пример проделанной работы:
|
В маленькой шведской деревушке Вестменхег жил когда-то мальчик по имени Нильс. |
7 мальчик
8 по имени Нильс
5 жил
1 в деревушке
2 маленькой
3 шведской
4 Вестменхег
6 когда-то
Мы строим дерево в текстовом редакторе, помещая корень дерева в начало строки, если у узла есть потомки, пишем их на следующих строках, используя отступы. Числа перед узлами здесь показывают порядок слов в изначальном предложении, чтобы словосочетания выводились более осмысленными.
Затем построенное дерево обрабатывается программой:
Энтропией здесь называется количество словосочетаний – поддеревьев, полученных из предложения.
Теперь, когда у нас появились способы быстро построить деревья и обработать полученную из них информацию, поставим перед собой задачу выяснить, можно ли как-то использовать эти инструменты при оценке сложности текста. Когда мы читаем какое-либо произведение, мы говорим, что оно простое, или наоборот, пока сложновато для нас. Разберем несколько текстов, сравним число возможных словосочетаний в каждом предложении и сравним полученные данные с их бытовой оценкой.
Были разобраны (примеры разбора приведены в приложении 1) по 20-40 предложений из четырех произведений: русская народная сказка «Вершки и корешки», «Красная шапочка» Шарля Перро, «Чудесное путешествие Нильса с дикими гусями» Сельмы Лагерлеф и «Волшебник изумрудного города» Александра Волкова. Обычно именно в таком порядке предлагается читать эти книги, от младшего дошкольного возраста до конца начальной школы. Возможно, это найдет отражение в наших подсчетах.
Как видно из полученных данных, приведенных в таблицах в приложении, текст, предназначенный для самых маленьких читателей, во-первых, имеет самое маленькое число узлов (в каждом предложении от 2 до 11 узлов), а во-вторых, число поддеревьев в каждом предложении колеблется от 3 до 66. При этом в остальных сказках есть предложения с чуть большим числом узлов, а число поддеревьев достигает 500 и более, даже предложения с 8 узлами могут иметь 69 поддеревьев. Для наглядности выведем в таблицу медианные значения количества сочетаний в каждом разобранном тексте:
|
Название текста |
Медианное значение количества сочетаний в тексте |
|
Вершки и корешки |
15 |
|
Нильс и дикие гуси |
20 |
|
Красная шапочка |
19 |
|
Волшебник Изумрудного города |
41 |
По полученным медианным значениям можем сделать вывод, что сказка «Вершки и корешки» является самой простой для восприятия. Сказки «Красная шапочка» и «Нильс и дикие гуси» имеют оценки выше, но примерно равные между собой. И самой трудной и более насыщенной уточнениями является сказка «Волшебник Изумрудного города». Данные выводы полностью соответствуют интуитивным оценкам произведений.
5Вывод
В моей исследовательской работе по математике на тему "Применение графов к решению задач" рассмотрены графы, области их применения, с помощью графов решено несколько математических и лексических задач. Также теория графов применяется в программировании.
Итак, если мы хотим решить большую, запутанную задачу с большим количество связей между частями в условии, представление этих частей и связей в виде графа может не только существенно облегчить решение, но и привести к неожиданным выводам, как это получилось на примере сравнения различных произведений.
Графы применяются в экономике, химии, физике, астрономии. технике, искусстве. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом. Об этом в данной работе не шла речь, но думаю, что в будущем я продолжу исследование применения графов в этих направлениях.
Как итог, я могу сказать, что достигла поставленных целей и показала практическую ценность теории графов.
Приложение 1. Примеры деревьев
Красная шапочка
Жила-была в одной деревне девочка красоты 6невиданной: мать любила её без памяти, а бабушка и того больше. F=38
Сшила как-то раз бабушка любимой внучке 6шапочку красного цвета и так сильно она девочке понравилась, что и снимать не хотелось. F=72
Всюду ходила она в своей шапочке, потому и стали называть её Красной Шапочкой. F=27
Раз испекла мама пирожки и говорит своей дочке. F=32
Сходи-ка ты навести бабушку, ей нездоровится. F=13
Нильс и дикие гуси
В маленькой шведской деревушке Вестменхег жил когда-то мальчик по имени Нильс. F=69
Сладу с ним не было никакого. F=10
Так прожил он до двенадцати лет. F=11
И тут случилось с ним необыкновенное происшествие. F=17
Вот как было дело. F=3
Вершки и корешки
Подружился как-то мужик с медведем. F=11
Вот и вздумали они вместе репу сеять. F=17
Посеяли и начали уговариваться, кому что брать. F=21
Я возьму себе корешки, а тебе, Мишка, достанутся вершки. F=17
Выросла у них хорошая репа. F=10
Волшебник Изумрудного города
Среди обширной канзасской степи жила девочка Элли. F=32
Жили они в небольшом фургоне, снятом с колёс и поставленном на землю. F=64
Степные ураганы не раз уже опрокидывали легонькое жилище фермера Джона. F=71
Около изгороди стоял длинный шест, на нём торчало соломенное чучело - отгонять птиц. F=35
Но Джон не унывал: когда утихал ветер, он поднимал домик, печка и кровати ставились на места, Элли собирала с пола оловянные тарелки и кружки - и всё было в порядке до нового
Приложение 2. Данные по количеству узлов и поддеревьев.
Вершки и корешки (среднее арифметическое значений количества поддеревьев 17, медианное 15)
|
кол-во корней |
кол-во сочетаний |
предложение |
|
4 |
11 |
Подружился как-то мужик с медведем. |
|
5 |
17 |
Вот и вздумали они вместе репу сеять. |
|
6 |
21 |
Посеяли и начали уговариваться, кому что брать. |
|
2 |
3 |
Мужик и говорит. |
|
7 |
17 |
Я возьму себе корешки, а тебе, Мишка, достанутся вершки. |
|
4 |
10 |
Выросла у них хорошая репа. |
|
3 |
6 |
Собрали они урожай |
|
7 |
17 |
Мужик взял себе корешки Мише отдал вершки. |
|
3 |
6 |
Видит медведь, что прогадал. |
|
6 |
21 |
Одни листья получил и говорит мужику. |
|
3 |
6 |
Ты, брат, меня надул. |
|
9 |
26 |
Ну, смотри, когда будем в другой раз сеять, ты уж меня так не проведешь. |
|
5 |
15 |
На другой год говорит мужик медведю. |
|
5 |
17 |
Давай, Миша, опять вместе сеять. |
|
11 |
66 |
Давай, только теперь ты себе бери вершки, а мне отдавай корешки – уговаривается Миша. |
|
3 |
6 |
Ладно! – говорит мужик. |
|
3 |
6 |
Пусть будет по-твоему. |
|
2 |
3 |
И посеяли пшеницу. |
|
3 |
6 |
Добрая пшеница уродилась. |
|
7 |
37 |
Мужик взял себе вершки, а Мише отдал корешки. |
|
10 |
42 |
Намолотил мужик пшеницы, намолол муки, напек пирогов, а медведь опять ни с чем. |
|
4 |
10 |
Сидит над ворохом сухих стеблей. |
|
6 |
21 |
Вот с тех пор перестали медведь с мужиком дружбу водить. |
Красная шапочка (среднее арифметическое значений количества поддеревьев 50,6, медианное 19)
|
кол-во корней |
кол-во сочетаний |
предложение |
|
13 |
38 |
Жила-была в одной деревне девочка красоты невиданной: мать любила её без памяти, а бабушка и того больше. |
|
14 |
73 |
Сшила как-то раз бабушка любимой внучке шапочку красного цвета и так сильно она девочке понравилась, что и снимать не хотелось. |
|
9 |
27 |
Всюду ходила она в своей шапочке, потому и стали называть её Красной Шапочкой. |
|
7 |
32 |
Раз испекла мама пирожки и говорит своей дочке. |
|
6 |
13 |
Сходи-ка ты навести бабушку, ей нездоровится. |
|
5 |
17 |
Да отнеси ей пирожки и горшочек масла. |
|
7 |
34 |
Смотри только в лесу не останавливайся и ни с кем не разговаривай. |
|
13 |
55 |
Красная Шапочка была послушной девочкой, она сейчас же собралась и отправилась к бабушке, которая жила в другой деревне. |
|
8 |
21 |
Идёт она по лесной тропинке и тут навстречу ей волк. |
|
10 |
82 |
Волк хотел было её съесть, да побоялся, потому что поблизости был слышен стук дровосеков. |
|
3 |
6 |
Вот он и спрашивает. |
|
4 |
10 |
Куда ты идёшь, Красная Шапочка? |
|
9 |
79 |
Бедная девочка забыла, что опасно в лесу останавливаться и разговаривать с волками, и отвечает ему. |
|
8 |
59 |
Иду к бабушке; несу ей пирожки да горшочек масла. |
|
4 |
10 |
А далеко живёт твоя бабушка? |
|
2 |
3 |
Спрашивает волк. |
|
14 |
70 |
- Очень далеко! - вон за той мельницей, что виднеется на опушке леса; а там будет первый дом как войдёшь в деревню. |
|
2 |
3 |
Отвечает Красная Шапочка. |
|
3 |
6 |
Говорит ей волк. |
|
5 |
15 |
- Знаешь, - пойду-ка и я навещу твою бабушку. |
|
12 |
31 |
Я пойду этой дорогой, а ты ступай по той: посмотрим, кто из нас быстрее дойдёт. |
|
12 |
51 |
И волк бросился изо всех сил бежать по самой короткой дороге, а девочка побрела неспеша по самой длинной. |
|
5 |
15 |
По пути она собирала букеты и напевала песенки. |
|
5 |
17 |
Прибежал волк первым к бабушкиному дому. |
|
1 |
1 |
Постучался: |
|
1 |
1 |
Тук, тук. |
|
2 |
3 |
Кто там? |
|
9 |
99 |
Это я, внучка ваша, Красная Шапочка, - принесла вам пирожки да горшочек масла. |
|
4 |
10 |
отвечал волк тоненьким голоском: |
|
8 |
53 |
Бабушка лежала в постели, потому что ей немного нездоровилось, и крикнула оттуда: |
|
5 |
9 |
Дёрни за верёвочку, дверь сама и откроется. |
|
5 |
9 |
Волк дёрнул за верёвочку, дверь открылась. |
|
9 |
94 |
Он бросился на старушку и разом проглотил её, потому что уже больше трёх дней ничего не кушал. |
|
17 |
594 |
Потом он запер дверь, улегся в бабушкину постель и стал поджидать Красную Шапочку, которая через некоторое время добрела до бабушкиного домика и постучалась: |
|
13 |
164 |
Услышав грубый голос, Красная Шапочка сперва было испугалась, но подумав, что видимо у бабушки голос осип из-за болезни, отвечала: |
|
5 |
17 |
Волк крикнул как только мог тонким голосом: |
Нильс (среднее арифметическое значений количества поддеревьев 43,4, медианное 20,5)
|
кол-во корней |
кол-во сочетаний |
предложение |
|
8 |
69 |
В маленькой шведской деревушке Вестменхег жил когда-то мальчик по имени Нильс. |
|
3 |
6 |
С виду - мальчик как мальчик. |
|
4 |
10 |
А сладу с ним не было никакого. |
|
4 |
11 |
Так прожил он до двенадцати лет. |
|
5 |
17 |
И тут случилось с ним необыкновенное происшествие. |
|
2 |
3 |
Вот как было дело. |
|
7 |
41 |
Однажды в воскресенье отец с матерью собрались на ярмарку в соседнее село. |
|
5 |
15 |
Нильс не мог дождаться, когда они уйдут. |
|
4 |
10 |
Нильс сделал два шага и остановился. |
|
3 |
6 |
С комнатой что-то случилось. |
|
17 |
71 |
Стены их маленького домика раздвинулись, потолок ушел высоко вверх, а кресло, на котором Нильс всегда сидел, возвышалось над ним неприступной горой. |
|
9 |
103 |
Чтобы взобраться на него, Нильсу пришлось карабкаться по витой ножке, как по корявому стволу дуба. |
|
13 |
62 |
Книга по-прежнему лежала на столе, но она была такая огромная, что вверху страницы Нильс не мог разглядеть ни одной буквы. |
|
7 |
37 |
Он улегся животом на книгу и пополз от строчки к строчке, от слова к слову. |
|
6 |
24 |
Он прямо измучился, пока прочел одну фразу. |
|
6 |
25 |
Так ведь и к завтрашнему дню до конца страницы не доберешься! - |
|
6 |
25 |
воскликнул Нильс и рукавом отер пот со лба. |
|
13 |
380 |
И вдруг он увидел, что из зеркала на него смотрит крошечный человечек - совсем такой же, как тот гном, который попался к нему в сетку. |
|
9 |
99 |
Только одет по-другому: в кожаных штанах, в жилетке и в клетчатой рубашке с большими пуговицами. |
|
4 |
11 |
- Эй ты, чего тебе здесь надо? - |
|
5 |
17 |
крикнул Нильс и погрозил человечку кулаком. |
|
7 |
34 |
Вот уж никогда не думала, что от муравьев такая беда может приключиться! |
|
7 |
28 |
Гусей-то они не трогают, знают, что гусь их не боится. |
|
4 |
11 |
Раньше я их не боялся, - |
|
2 |
3 |
обиделся Нильс. - |
|
4 |
11 |
Раньше я никого не боялся. |
Волшебник изумрудного города (среднее арифметическое значений количества поддеревьев
54,3, медианное 41)
|
кол-во корней |
кол-во сочетаний |
предложение |
|
7 |
32 |
Среди обширной канзасской степи жила девочка Элли. |
|
11 |
50 |
Ее отец фермер Джон, целый день работал в поле, мать Анна хлопотала по хозяйству. |
|
8 |
64 |
Жили они в небольшом фургоне, снятом с колёс и поставленном на землю. |
|
11 |
19 |
Обстановка домика была бедна: железная печка, шкаф, стол, три стула и две кровати. |
|
7 |
36 |
Рядом с домом, у самой двери, был выкопан «ураганный погреб». |
|
5 |
17 |
В погребе семья отсиживалась во время бурь. |
|
8 |
71 |
Степные ураганы не раз уже опрокидывали легонькое жилище фермера Джона. |
|
21 |
69 |
Но Джон не унывал: когда утихал ветер, он поднимал домик, печка и кровати ставились на места, Элли собирала с пола оловянные тарелки и кружки - и всё было в порядке до нового урагана. |
|
5 |
15 |
Элли шла уже несколько часов и устала. |
|
9 |
87 |
Она присела отдохнуть у голубой изгороди, за которой расстилалось поле спелой пшеницы. |
|
10 |
35 |
Около изгороди стоял длинный шест, на нём торчало соломенное чучело - отгонять птиц. |
|
14 |
90 |
Голова чучела была сделана из мешочка, набитого соломой, с нарисованными на нём глазами и ртом, так что получалось смешное человеческое лицо. |
|
11 |
41 |
Чучело было одето в поношенный голубой кафтан; кое-где из прорех кафтана торчала солома. |
|
16 |
128 |
На голове была старая, потёртая шляпа, с которой были срезаны бубенчики, на ногах - старые голубые ботфорты, какие носили мужчины в этой стране. |
|
18 |
217 |
Когда Дровосек заметил, что Страшила опирается на корявую, сучковатую дубину, он тотчас срезал с дерева прямую ветку и сделал для товарища удобную крепкую трость. |
|
9 |
71 |
Скоро путники пришли к месту, где дорога заросла кустарником и стала непроходимой. |
|
8 |
47 |
Но Железный Дровосек заработал своим огромным топором и быстро расчистил путь. |
|
7 |
28 |
Элли шла, задумавшись и не заметила, как Страшила свалился в яму. |
|
5 |
17 |
Ему пришлось звать друзей на помощь. |
|
8 |
44 |
Нелегко было двум друзьям взвалить тяжелого Льва на телегу. |
|
13 |
143 |
Но они все же подняли его, и мыши с помощью Страшилы и Железного Дровосека быстро вывезли телегу с макового поля. |
|
8 |
36 |
Лев был привезён на полянку, где сидела Элли под охраной Тотошки. |
|
10 |
107 |
Девочка сердечно благодарила мышей за спасение верного друга, которого успела сильно полюбить. |
|
9 |
45 |
Мыши перегрызли нитки, привязанные к их хвостам, и поспешили к своим домам. |
|
6 |
28 |
Королева-мышь подала девочке крошечный серебряный свисточек. |
|
12 |
33 |
- Если я буду вам нужна снова, - свистните трижды в этот свисток, и я - к вашим услугам. |
|
2 |
3 |
сказала она. |
|
1 |
1 |
До свидания! |
|
2 |
3 |
Ответила Элли. |
Список литературы
|
[1] |
Ан.В. Погребной, В.К. Погребной, «Инвариант графа на основе компактных подграфов и алгоритм его вычисления,» Известия Томского политехнического университета, т. 322, № 5, 2013. |
|
[2] |
N. Sloane, «OEIS A000081. Number of unlabeled rooted trees with n nodes.,» [ВИнтернете]. Available: https://oeis.org/A000081. |
|
[3] |
Е.И. Большакова, К.В. Воронцов, Н.Э. Ефремова, Э.С. Клышинский, Н.В. Лукашевич, А.С. Сапин, Автоматическая обработка текстов на естественном языке и анализ данных, М.: НИУ ВШЭ, 2017. |
|
[4] |
«АОТ. Автоматическая Обработка Текста.,» [В Интернете]. Available: http://aot.ru/demo/graph.html. |
|
[5] |
В.Н. Касьянов, В.А. Евстигнеев, Графы в программировании: Обработка, визуализация и применение., Спб.: БХВ-Петербург, 2009. |
|
[6] |
Л. Прокушев, Основы теории графов и алгоритмизации задач, Спб., 2000. |
|
[7] |
А. Жмудь, «Теория графов – применение в логистике (история, основы теории, линейная транспортная задача),» 2015. [В Интернете]. Available: http://urok.1sept.ru/статьи/656970/. |
|
[8] |
В. Данькова, «Факультативный курс по математике «Графы» для 5-6 классов,» 2018. [В Интернете]. Available: https://multiurok.ru/files/fakultativnyi-kurs-po-matematike-grafy-dlia-5-6-kl.html. |
|
[9] |
«НКРЯ. Национальный корпус русского языка. Синтаксический корпус.,» [В Интернете]. Available: http://www.ruscorpora.ru/new/search-syntax.html. |