ка

Цели и задачи проекта
Проиллюстрировать применение математики на практике
Показать связь с другими областями знаний
Познакомить с историческими сведениями
Подчеркнуть эстетические аспекты изучаемых вопросов

Понятие графов
Всем известно, что слово «граф» означает дворянский титул, например граф Лев Николаевич Толстой. А вот в математике графом называют набор точек некоторые из которых соединены линиями. Точки именуются вершинами графа, а отрезки – рёбрами.
На рис.1 изображён граф хорошо известный москвичам. Это схема московского метро: вершины - конечные станции и станции пересадок, рёбра пути, соединяющие эти станции. На рис.2 вы видите ещё один граф – часть генеалогического дерева графа Льва Николаевича Толстого. Здесь вершины – предки писателя, а рёбра показывают родственные связи между ними.

Немного из истории
Появление теории графов как математической дисциплины, все единодушно относят к 1736 году, когда Л. Эйлер (1707-1782, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук), решил широко известную в то время задачу о Кёнигсбергских мостах. Подробнее об этой задаче будет сказано ниже. Этот результат более ста лет оставался единственным в теории графов.

Примерно в середине XIX века немецкий физик Г. Кирхгоф (1824-1871, иностранный член-корреспондент Петербургской академии наук разработал теорию деревьев (специальный вид графов) для исследования электрических цепей, а английский математик А.Кэли решил перечисленные задачи некоторых типов деревьев для описания строения углеводородов. В настоящее время эта теория широко развита и успешно применяется.
Немного из истории

Немного из истории
Ещё одна проблема была сформулирована в середине XIX века – проблема четырёх красок. Первоначально она формулировалась в терминах раскраски географической карты так, чтобы любые две страны на карте, имеющие общую границу, были окрашены разными цветами. Эта проблема легко сводится к формулировке в терминах теории графов. (рис.3)
По-видимому, постановкой этой проблемы мы обязаны немецкому математику А.Мёбиусу (1799-1868, устное сообщение на лекциях в 1840 году). Известно также, что проблему пытались решить и другие известные математики, например, А.Де Морган, А.Кэли, причём последний в 1878 году сообщил, что не может её решить, и опубликовал формулировку этой проблемы в трудах Лондонского Королевского общества.

Немного из истории
Среди работ первой половины XX века непосредственно относящихся к теории графов или существенно использующих её, можно выделить следующих.
Критерий планарности графа доказали независимо друг от друга академик Российской Академии наук Л.С.Понтрягин в 1927 году и польский математик К.Куратовский в 1930 году (понятия планарного и плоского графа будут введены ниже).
Немецкий математик Д.Пойя предложил метод производящих функций, позволяющих решать задачи подсчёта графов, Встречающихся в различных областях науки.
Метод чередующихся цепей, идея которого восходит ещё к Е.Эгевари и который под названием «венгерского метода» и теперь успешно применяется в некоторых разделах теоретической и прикладной математики.

Немного из истории
Важнейшим событием для теории графов этого времени было появление в 1936 году монографии австрийского математика Д.Кинега «Теории конечных и бесконечных графов», к сожалению, не переведённой на русский язык.
1948 году в «Успехах математических наук» опубликована работа «О некоторых математических вопросов теории электрических цепей», в которой успешно использованы графы. Автор этой работы ныне член-корреспондент Российской Академии наук Л.Д. Кудрявцев.
Вторая половина XX века с точки зрения развития графов существенно отличается от первой его половины. Во-первых, теория графов была признана математиками как самостоятельная математическая дисциплина.

Появились не только монографии К.Бержа «Теория конечных графов и её применение», 1962 (1958, Париж); О.Оре «Теория графов», 1968 (1962, Американское математическое общество); Зыкова А.А. «Основы теории графов» (1987,Москва, Наука); Ф.Харрари «Теория графов», 1973 (1969, Лондон), но и популярные книги О.Оре «Графы и их применение», 1965 (1963, Нью-Йорк) и другие.
Во-вторых положение сильно изменилось с связи с появлением малогабаритными, быстродействующими и надёжными ЭВМ, бурным развитием математической логики, машинной математике, автоматики, кибернетики, теории информации,
Немного из истории
математической экономики, теории игр исследования операций математической лингвистики и других областей, где, в отличии от классического анализа непрерывных величин.

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

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

Задача о Кёнигсбергских
мостах
Как уже говорилось выше, основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах.
Бывший Кёнигсберг(ныне Калининград)расположен на реке Прегель. В пределах города река омывает 2 острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кёнигсберцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только 1 раз.
Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход он начертил упрощённую схему мостов. Получился граф, вершины которого–части города, а рёбра–мосты(рис.4).

В итоге Эйлер доказал общее утверждение: для того чтобы обойти все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнения следующих двух следующих утверждений:
1) из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (графы, удовлетворяющие этому требованию, называют связными);
из каждой вершины должно выходить чётное количество рёбер.
2) Замкнутый путь, проходящий по одному разу по всем рёбрам графа, называют с тех пор эйлеровым циклом.
Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать - в другой.

Возможно, многим подобного рода задачи знакомы ещё по журналам «Мурзилка», «Весёлые картинки» и др. Там предлагалось начертить какую-нибудь фигуру, не отрывая карандаша от бумаги и не проводя дважды по одной линии. На рис.4 и 5 приведены две такие фигуры. Первая из них называется «Сабля Магомета». В ней существует эйлеров цикл, так как из шести вершин графа выходит чётное количество рёбер. Вторая фигура – «Распечатанное письмо» - имеет две вершины (нижние), из которых выходит нечётное количество рёбер. Поэтому рисунок нужно начинать с одной из них, а в другой – заканчивать.
А как же обстоит дело с кёнигсбергскими мостами? Здесь при каждой из четырёх вершин нечётное число рёбер, так что нет не только эйлерова цикла, но и пути из одной вершины в другую, проходящего по всем рёбрам графа.
рис.5
рис.4

В 1859 г. английский математик Уильям Гамильтон выпустил в продажу головоломку. Она представляла собой деревянный додекаэдр (12-гранник), в вершинах которого вбиты гвоздики (рис.6). Каждая из 20 вершин была помечена название одного из крупных городов мира – Дели, Брюссель, Кантон и т. д. Требовалось найти замкнутый путь, проходящий по рёбрам додекаэдра и позволяющего побывать в каждой его вершине по одному разу. Путь следовало отмечать с помощью шнура, зацепляя его за гвоздики.
Игрушка не имела такой популярности, какой ещё недавно пользовался «кубик Рубика», но оставила след в математике. Замкнутый путь по рёбрам графа, проходящий по одному разу через все вершины, называют гамильтоновым циклом. В отличие от эйлерова цикла условия существования на произвольном графе гамильтонова цикла до сих пор не установлены.
Графы изоморфные и плоские

Если поставить проволочный додекаэдр на плоскость, а затем поднести источник света к центру его верхней грани (рис.7), то проекции-тени рёбер на плоскость составят граф (рис.8).
Из опытов с проекцией видно, что свойства графов не меняются с изменением положения его вершин, не зависят от того, какими линиями они соединены. Два графа, изображённых на рис.9, в этом смысле одинаковы: у них одинаковое число вершин и если две вершины одного графа соединены ребром, то вершины второго графа, имеющие те же номера, тоже соединены ребром. Это замечание более строго формулируется так: да графа называются изоморфными (от греческого «изос» - равный, «морфе» - вид, форма), если между их вершинами можно установить взаимно однозначное соответствие, при котором вершинам, соединенным ребром, соответствуют вершины, также соединённые ребром.

В трёх избушках жили трое друзей. Около их домиков находилось три колодца: один с солёной водой, второй – со сладкой, а третий – с пресной. Но однажды друзья поссорились, да так, что и видеть друг друга не хотели. И решили они по-новому проложить тропинки от домов к колодцам, чтобы их пути не пересекались. Как это сделать? На рис.13 проведено восемь из девяти тропинок, но провести девятую уже не удаётся.
Задача "Домики-колодцы"
рис.13
Мы знаем, что у изоморфных графов некоторых ребра пересекаются. А всегда ли граф можно изобразить на плоскости так, чтобы его рёбра не пересекались? Оказывается, нет. Графы, для которых это возможно называются плоскими.
Давайте рассмотрим задачу с плоскими графами

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

Плоские графы обладают многими интересными свойствами. Так, Эйлер обнаружил простую связь между количеством вершин (B), количеством рёбер (Р) и количеством частей (Г) на которые разделяется плоскость:
В – P + Г = 2
Если вспомнить, как с помощью лампочки плоский граф, изоморфный графу, состоящему из вершин и рёбер выпуклого многогранника, то легко понять, что эта формула верна для любого выпуклого многогранника. Этот факт, как недавно выяснилось, был известен ещё Рене Декарту.

Во многих случаях применения графов рёбра, соединяющие вершины, имеют чётко выраженное направление. Так на графах генеалогических деревьев направление, естественно, идёт от родителей к детям. Поэтому на фрагменте генеалогического древа (рис.15), где буквой M обозначаются мужчины, а буквой W – женщины, видим, что у супружеской пары M1 и W2 есть сын, но у супруга есть ещё двое детей (девочка и мальчик) от первого брака с W1.
Графом является и система улиц города. Его вершины – площади или перекрёстки, а рёбра – улицы. В больших городах на некоторых улицах устанавливается одностороннее движение. Естественно, что такой граф должен иметь направленные рёбра. Тогда улицы с двухсторонним движением можно обозначить парами рёбер с противоположным направлением.
Направленные графы

Графы, в которых все рёбра имеют направление, называются орграфами. На них удобно рассматривать различные транспортные задачи. Например, между городами A и B имеется сеть дорог. И на некоторых из них одностороннее движение (рис.16). Кроме того, задана пропускная способность каждой дороги, скажем, в тысячах машин в час. Попробуем ответить на вопрос: какой максимальный поток возможен из A в B и из B в A?
Как видим, хотя из A может выезжать в час 7 тыс. машин, но въехать в B могут только 4 тыс. из них. Несложно проверить, что 4 тыс. машин в час остальные дороги в состоянии пропустить.
С другой стороны, из B в A могут выехать 3 тыс. машин в час, однако въехать в A смогут лишь 2 тыс. Поток в 2 тыс. машин из B в A остальные дороги, как нетрудно убедиться, также смогут пропустить.
Орграфы

Если граф дорог боле сложен, то найти решение уже не легко. Были придуманы алгоритмы, позволяющие с помощью компьютера или без него определить максимально возможный поток между двумя вершинами орграфа, если указана пропускная особенность каждого из его рёбер.
Вот ещё одно применение орграфа. При составлении больших проектов, содержащих различные виды работ, часто возникает ситуация, когда ту или иную работу можно начать лишь по окончании других. Так, при строительстве дома нельзя приступить к отделочным работам, пока не возведены стены, и нельзя возводить стены, до укладки фундамента. Последовательность работ изображается в виде орграфа (рис. 17). Здесь вершины – производимые работы (с указанием их продолжительности), а стрелки указывают, какие из них могут выполняться только по окончании предыдущих. Такие орграфы называются сетевыми графиками. Они применяются при планировании деятельности предприятия.

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

Ориентированные графы
Ориентированный граф - это граф, на ребрах которого обозначены разрешенные направления движения, проще говоря, расставлены стрелочки. Такая, на первый взгляд "мелочь" настолько сильно меняет идеологию решения задач, что ориентированные графы мы рассматриваем отдельно от неориентированных.
В обычных графах мы рассматриваем такие фундаментальные понятия, как степень вершины, путь и цикл, компонента связности. Для ориентированных графов их надо существенно модифицировать:
- ребро входит в вершину, если по нему можно двигаться в направлении к этой вершине, и выходит из вершины, если по нему можно двигаться в направлении от этой вершины;
- входящая степень вершины - это число входящих в нее ребер;
- исходящая (или выходящая) степень вершины - это число выходящих из нее ребер;
- путь из вершины A в вершину B - это последовательность ребер и промежуточных вершин, по которым можно дойти из A в B; длина пути определяется, как обычно (число ребер); простой путь - как обычно, путь, в котором вершины (и тем более, ребра) не повторяются;

- ориентированный цикл - это замкнутый простой путь в ориентированном графе;
- сильно связный ориентированный граф - это ориентированный граф, где из любой вершины в любую есть путь (для каждой пары вершин A и B есть как путь из A в B, так и путь из B в A);
- компонента сильной связности - это часть графа, которая сама по себе сильно связна, но ее нельзя расширить так, чтобы она осталась сильно связной; между разными компонентами сильной связности могут быть ребра, но все ребра между двумя разными компонентами направлены в одну и ту же сторону.
В задачах на ориентированный граф обычно упоминаются всякие реки, потоки или дороги с односторонним движением. Иногда - односторонние отношения между людьми ;-)
Задача 1. Барон Мюнхаузен, прилетев с Луны, рассказал, что в каждое лунное море впадает пять рек, а из каждого лунного моря вытекает шесть рек. Докажите, что он говорит неправду.
Решение: Пусть на Луне N морей. Посчитаем реки двумя способами: по тому, откуда они вытекают, и по тому, куда они впадают. Первым способом получается, что рек 6N, а вторым - что 5N. Противоречие, ч.т.д.
(!) Аналогичным рассуждением доказывается, что в ориентированном графе сумма входящих степеней равна сумме исходящих, так как каждая из них равна числу ребер. Действительно, у каждого ориентированного ребра одно начало и один конец (сравните с утверждением про сумму степеней вершин обычного графа!).
Решение задач с помощью ориентированных графов

Задача 2. В королевстве каждый город соединен с каждым дорогой. Может ли сумасшедший король ввесте на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться?.
Решение: Тут мы имеем дело с другим видом задач: введением ориентации (с заданными свойствами) на обычном графе. Попробуем придумать простенькие примеры (см. рис.).
Интересно... в каждом примере все ребра идут именно слева направо (особенно легко это получается, если каждый следующий пример строить как расширение предыдущего!). Так давайте всегда проводить все ребра слева направо (при этом избегая рисовать вершины в точности друг над другом). Тогда, выехав из любого города, мы будем оказываться все правее и правее, и никогда не вернемся в исходную точку. Значит, можно.
Можно формализовать это и без геометрических соображений о том, как нарисован граф: занумеровать все вершины и ставить все стрелки от меньшего номера к большему.
Замечание. В построенном графе каждая вершина - отдельная компонента сильной связности.

Требуются, требуются,
требуются...
Представим себе, что организуется географическая экспедиция на острова Тихого океана. В её состав кроме начальника должны войти 3 географа, повар, радист, врач и техник. Участвовать в экспедиции изъявили желание десять человек, причём каждый владеет одной или несколькими из этих профессий. Всегда ли начальник экспедиции сможет из такой группы набрать нужных ему специалистов?
Нарисуем граф, у которого две группы вершин: десять соответствуют претендентам и семь – должностям. Рёбрами соединим вершины претендентов с вершинами их специальностей (рис.18).
Казалось бы, всё в порядке, на каждое место есть кандидат. Однако впечатление это обманчиво. Посмотрите: на должность врача имеется лишь один претендент (№3), разумеется, он её и займет. Но тогда на три места географов останутся только 2 претендента. Таким образом, из этой группы желающих не удастся собрать команду экспедиции.

Мы рассмотрели специфический граф. Его вершины распадаются на два множества, такие, что вершины одного и того же множества не соединены между собой рёбрами. Такие графы называются двудольными. Двудольным является и граф «домики – колодцы».
Теперь заглянем на биржу труда. Сюда пришли семь человек. Им предложили десять рабочих мест по тем специальностям, которыми они владеют. Снова нарисуем двудольный граф соответствия людей и профессий (рис.19). Этот граф похож на предыдущий, только люди и вакансии поменялись местами. Смогут ли все семеро получить работу по специальности?

Каждая фраза русского языка членится на составляющие. Мелкие составляющие входят в более крупные. Такое членение фразы на составляющие обеспечивает возможность понимания фразы. Наша языковая составляющая позволяет нам довольно легко выделять эти составляющие. Рассмотрим примеры: здесь составляющие выделены скобками
«(Все1 это2) (сильно3 (поколебало4 (мою5 (авторскую6 уверенность7))))»
В сущности кавычки здесь также могут играть роль скобок, выделяющих максимальную составляющую. В число составляющих мы будем включать и отдельные слова, которые обозначим Х, L. В рассмотренном примере мы выделим следующие составляющие:
L1= (х1, х2, x3, х4, х5, х6, х7)
L2 = (х1, x2)
L3 = (х3, х4, х5, х6, х7)
L4 = (х3, х4, х5, x6, х7)
L5 = (х5, х6, х7)
L6 = (х6, х7)
Граф составляющий
Изобразим данное отношение с помощью графов:
Этот граф является несимметричным деревом, которое наиболее ветвится вправо.

Рассмотрим еще одно дерево составляющих на примере предложения: «Важные лингвистические открытия нередко незаслуженно отвергались». Выделим сначала группу подлежащего: «важные лингвистические открытия» и группу сказуемого: «нередко незаслуженно отвергались». Группа подлежащего далее делится на составляющие: «важные» и <лингвистические открытия». Лингвистические открытия на «лингвистические» и «открытия». Таким же образом группа сказуемого делится на составляющие. Процесс и результаты деления наглядно представляются в виде дерева составляющих. Поскольку дерево отражает деление на части, ясно, что от каждого узла должно отходить более одной дуги (это важное свойство дерева составляюгцих). Изобразим дерево составляющих в виде скобочной записи ((Важные (лингвистические открытия)) (нередко (незаслуженно отвергались))).
Скобную запись дерева составляющих можем построить только для такого дерева, у которого для любых двух слов, входящих в какую-либо одну составляющую, все слова между ними входят в ту же составляющую.

Между словами, образующими правильную русскую фразу, существуют различные лингвистические отношения. Указать явным образом эти отношения — это и значит описать синтаксическую структуру фразы. Одно из важнейших типов отношений — это грамматическое управление.
Обозначим его символом ( )Оно является асимметричным отношением. Согласно сложившейся традиции, считается, что управление идет от определяемого к определению, от сказуемого к подлежащему, от предлога к существительному, от глагола к прямому дополнению, от глагола к предлогу.
Рассмотрим, как расставляются управления на конкретной фразе с нумерацией слов:
«И1 сатана2 привстав3 с4 весельем5 на6 лике7 лобзанием8 своим9 насквозь10 прожег11 уста12 в13 предательскую14 ночь15 лобзавшие16 Христа17».
Граф управления

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

Математическое свойство «древесности» трудно совместить с его синтаксической структурой, в том смысле, что дерево подчинения (это дерево, отражающее синтаксическое подчинение одних синтаксических единиц другим) не отражает всех возможных синтаксических связей в предложении. Одна из причин этого состоит как раз в том, что формальное подчинение часто не согласовано со смысловым. То есть нам нужно каким-либо образом линейно упорядочить узлы дерева. Если бы все узлы дерева всегда можно было изобразить в виде точек, лежащих на одной прямой, то это было бы сделать просто, ведь точки на прямой уже линейно упорядочены. Но изображение дерева имеет сложную конфигурацию. Поэтому для упорядочения узлов дерева используют особую прямую, лежащую вне дерева и называемую направляющей прямой дерева, а также операцию проекции узлов дерева на эту прямую.
Граф подчинения

А синтаксическое дерево подчинения называют расположенным относительно направляющей прямой, если при проекции на эту прямую никакие два узла дерева не проектируются в одну точку. Для любого дерева подчинения найдется такая прямая, относительно которой это дерево будет расположено. Содержательно направляющая прямая соответствует линейному порядку слов в предложении. Расположение дерева подчинения называется проектированием, если при указанном соглашении перпендикуляры, опущенные из узлов на направляющую прямую не «задевают дерево», т.е. ни один из этих перпендикуляров не пересекает ни одной дуги. Проективные деревья имеют правильное расположение слов в предложении, а непроективность дерева отвечает не вполне удачному расположению слов во фразе.
Но не следует думать, что проективность сама по себе всегда обеспечивает правильный порядок слов. Речь идет о поэзии, свободной от многих форм обычного языка. Благодаря непроективным структурам достигается возвышенность приподнятого стиля, например, в стихотворении А.С. Пушкина.

С интуитивной точки зрения, решение вопроса о том, проста фраза или тяжеловесна, не составляет труда. Мы обычно не останавливаемся в размышлениях, читая в книгах высказывания типа «Чехов пишет легко и просто, а язык Толстого тяжеловесен». Но давайте задумаемся над этой фразой. Основное утверждение синтаксической теории громоздкости состоит в том, что чем больше обрамление в дереве подчинения, тем более тяжеловесной выглядит фраза, это может быть неудачный порядок слов, или большое число дополнительных связей в предложении.
Теория громоздкости

Теперь давайте определим, как фразы одного писателя или поэта отличаются от других. А точнее, при анализе художественного текста можно использовать математические методы. Покажем на примере творчества нескольких писателей, как на язык деревьев переводятся трудноуловимые, и на первый взгляд неформализуемые особенности стиля, которые кладутся в основу стилистической диагностики. Например, основная черта синтаксиса прозы А.С. Пушкина — её ритмизованность и подчиненный ей лаконизм выражений. В прозаических произведениях Пушкина преобладают краткие фразы, часто встречаются нераспространенные предложения. Так если взять «Капитанскую дочку», то для неё типично расположенное дерево подчинения следующего вида:
Теория графов и анализ
художественного текста

Пушкинский текст в основном состоит из предложений, в которых не более 11 слов, а рисунки этих деревьев либо симметричны, либо имеют длинный правый отросток. При этом даже для длинных фраз громоздкие деревья практически не возникают. Как мы видим, интуитивное ощущение прозаичности пушкинской фразы соответствует строгому понятию синтаксической простоты.
Деревья Лермонтовской прозы во многом похожи на пушкинские, хотя расчеты показывают, что в среднем предложения Лермонтова чуть-чуть длиннее и чуть-чуть сложнее. Впрочем, есть важное различие в рисунках деревьев, свойственных этим авторам. Ширина ветвления корня дерева для фразы из «Героя нашего времени» гораздо больше, чем для фразы из «Капитанской дочки». Это означает, что дерево лермонтовской фразы растёт вширь, в то время как в пушкинской фразу оно растёт вглубь. Большая ширина ветвления возникает вследствие того, что сказуемые в лермонтовской фразе подчиняют себе не только дополнения, но и разнообразные по структуре и значению обстоятельства.

У Н.В. Гоголя в «Вечерах на хуторе близ Диканьки» в стилистической пестроте фраз встречаются не только короткие предложения. Здесь в большом количестве представлены предложения сложные по структуре. Даже относительно короткие предложения из 6-12 слов строятся у Гоголя весьма разнообразно, в его произведениях можно найти едва ли не любую теоретически возможную из данного числа слов конфигурацию ветвей дерева. Наблюдается своеобразный тип структуры с многократными зигзагами когда, спускаясь вниз по стрелкам, мы постоянно изменяем направление движения.

Сравнив прозу Л.Н. Толстого и Ф.М. Достоевского, можно отметить, что стилю обоих писателей присущи деревья достаточно сложной конфигурации. Но фразы Л.Н. Толстого мы опишем скорее, как громоздкие, а построения Достоевского как «неупорядоченные». Язык Толстого тяжеловесен, а язык Достоевского хаотичен. Как же переводится эта оценка современного писателя на формальный язык деревьев? Громоздкость синтаксиса Толстого сказывается в значительном ветвлении деревьев влево (что повышает глубину дерева); хаотичность синтаксиса Достоевского — в большом числе зигзагов в правой части дерева.

А теперь выясним, по какому принципу лингвисты поводят анализ художественного текста. И.П. Севбо привел семь таких признаков, мы приведём для примера четыре.
Количество узлов дерева (т.е. количество слов во фразе)
Количество простых предложений в сложном (помечание стрелок, соответствующих связям между частями сложного предложения)
Число уровней в дереве (длина самого длинного из путей дерева)
Ширина ветвления корня (число узлов подчиненных корню)
Проведем эксперимент. Перед нами строки из произведения «Кавказский пленник» А.С. Пушкина и М.Ю. Лермонтова. Нам нужно определить, какой граф принадлежит Пушкину, а какой Лермонтову. Мы это сделаем с помощью Севбо.
Признаки И.Л. Севбо

Как видите, с помощью графов, зная особенности стиля того или иного писателя, можно определить, кому принадлежит фраза.
Из данных таблицы ясно, что дерево на рисунке В сложнее дерева на рисунке А. Как было сказано выше, язык Лермонтова немного сложнее языка Пушкина. Следовательно, граф на рисунке А принадлежит А.С. Пушкину, а граф на рисунке Б — М.Ю. Лермонтову.

Мы часто читаем произведения, переведенные с иностранного языка, но никогда не задумываемся над тем, насколько точен этот перевод. Ведь структура строения предложения переводчика должна быть похожа на авторскую. От этого много зависит. Представьте, например, что перед вами текст писателя, язык которого достаточно прост, т.е. нет громоздких предложений. Если перевод этого текста будет делать писатель, который любит строить сложные предложения, то будет уже что-то не то, даже если перевод очень точен. Поэтому, я задумался над тем, насколько точны (т.е. насколько схожа структура предложений автора и переводчика) переводы. Это я проверил с помощью теории графов. Возьмем 73 сонет В. Шекспира и З перевода: В. Бенедиктова, В. Брюсова и Б. Пастернака и сделаем анализ. Для этого начертим графы строк, но сначала познакомимся с произведениями этих авторов.
Графы и стилистика
переводов иностранных текстов

1. В. Шекспир.
That time of year thou mayst in me be hold
When yellow leaves, or none, or few do hang
Upon those boughs which shake against the cold
In me thou seest the twilight of such day
As after sunset fadeth in the west
Which by and by black night doth take away,
Death’s second self that seals up all the rest.
In my thou seest the glowing of such fire,
That on the ashes of his youth doth lie,
As the death-bed, whereon it must expire,
Consumed with that which it was nourished by.
This thou perciev’st, which makes thy love more strong,
To love that well, which thou must leave ere long.
2. Б. Пастернак.
То время года видишь ты во мне,
Когда из листьев редко, где какой,
Дрожа, желтеет в веток голизне,
А птичий свист везде сменил покой.
Во мне ты видишь бледный край
небес,
Где от заката памятка одна
И, постепенно взявши перевес,
Их отпечатывает темнота.
Во мне ты видишь то сгоранье дна,
Когда зола, что пламенем была,
Становится могилою огня,
А то, что грело, изошло дотла
И, это видя, помни: нет цены
Свиданьям, дни которых сочтены.

3. В. Брюсов.
То время года видишь ты во мне,
Когда, желтея, листья стали редки,
И там, где птицы пели о весне,
Оголены , дрожа от стужи, ветки.
Во мне ты сумерки находишь дня,
Что гаснет после яркого заката;
Ночь тёмная, к покою всех клоня
(Двойник твой Смерть!), его влечет куда-то!
Во мне ты видишь отблески огней,
Лежавших в пепле юности своей;
Они окончат жизнь на том ложе.
Снедаемые тем, что их запекло,
И потому, что день ты любишь строже,
Спеши любить то, что почти прошло!
4. В. Бенедиктов.
Во мне перед собой ты видишь время снега,
С кустов зеленая одежда их снята,
Певцов пернатых нет, в оркестре пустота.
Поблёклый лист упал, исчезла песен нега -
Во мне перед собой ты видишь час ночлега,
На западе дрожит чуть светлая черта,
И всё густеет мрак, мрак — этот after ego
Тьмы смертной, вечной тьмы, недалека и та.
Во мне перед тобой дней прошлых лишь остаток,
Лишь искры над золой, а пламень прекращен,
Убитый тем, чем жил и чем питался он.
Люби ж меня сильней! Ты видишь: срок мой краток,
Ты потерять меня страшишься — миг лови!
Чем больше этот страх, тем больше дай любви!

Теперь начертим графы нескольких строк эти стихотворений.
1. Шекспир
2. Пастернак

3. Брюсов
4. Бенедиктов

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

А теперь наложим графы текстов перевода на граф оригинала.
После наложения, щёлкните мышью

Анализируя графы с помощью признаков Севбо, я выяснил, что для текста Шекспира, в плане перевода, более близки Бенедиктов и Пастернак. У Брюсова по сравнению с Шекспиром, язык легче. Но после наложения графов на граф я увидел , что у графов Бенедиктова и Шекспира есть большие несоответствия, в то время как у Шекспира с тем же Брюсовым графы очень схожи. Проведя этот анализ, я выяснил, что Брюсов более точно передал смысл сонета Шекспира. А по характеру написания более близок к писателю сонет Пастернака, так как язык Пастернака и Шекспира во многом схож.

Заключение
В этой презентации мы познакомились с различными сведения о графах, начиная с определения и простейших задачек, решенных с помощью теории графов, и заканчивая моим научным исследованием перевода 73 сонета Шекспира известнейшими поэтами России В. Бенедиктова, В. Брюсова и Б. Пастернака. В результате, которой я узнал, что ближе всех к великому писателю сонет оказался поэт В. Брюсов и Б. Пастернак. Кроме того, в этой презентации мы познакомились с различными видами графов, попрактиковались в анализе художественного текста, в стилистике переводов иностранных текстов и увидели, как на практике, и в жизни широко используется теория графов.

Список источников:
Энциклопедия для детей, том 11 Математика, Москва, «Аванта+», 1998 год.
Математика. Еженедельное учебно-методическое приложение к газете Первое сентября», №15 (16-22 апреля 2001 г), Москва, издательство «ОЦ КУДИЦ-ОБРАЗ».
Оре Ойстин «Графы и их применение» М, 1965
Саркисян А.А., М.Ю. Колягин «Познакомьтесь с топологией» М.,1976
Липатов Е. П. «Теория графов и её применение», 1986
Берж К. «Теория графов и её применение», 1962
Верезина Л.Ю. «Графы и их применение», 1979

Оре Ойстин «Теория графов», 1980
Уилсон Р. «Введение в теорию графов», 1977
Зыков Л.А. «Основа теории графов», 1987
Крейдлин Г.Е. «Математика помогает лингвистике», 1994
Басанер Р. И Саити Т. «Конечные графы и сети» М, 1971
Шрейдер Ю.А. «Равенство, сходство, порядок» М, 1971
Сайт в Интернете
http://acadclasses.narod.ru/math/lectures.htm