Графы с цветными ребрами.

Министерство образования и науки Российской Федерации

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

«Лицей №14 имени Заслуженного учителя Российской Федерации А.М.Кузьмина»

Проектная работа

По дисциплине: математика

Тема: «Графы с цветными ребрами»

Выполнил:

учащийся 10 класса «А»

Александров Никита Владимирович

Подпись           

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

Неверовская Светлана Владимировна

Оценка        

Дата        

Подпись        

Тамбов - 2015

СОДЕРЖАНИЕ

Введение

При решении математических, физических задач, головоломок нам часто приходится делать чертежи, которые представляют собой различные фигуры, имеющие точки,  соединенные линиями. При этом создаются таблицы, модели, рисунки, где выявляются определенные закономерности, т.е. возникает геометрическая схема, представляющая собой систему линий, связывающих какие-то заданные точки. Данная схема получила определение графа. В теории графов точки называются вершинами, а связывающие их линии – ребрами. Теория графов обосновывает способы построения графов, выражающих зависимости или связи в форме геометрических схем между различными единицами той или иной совокупности. Данная теория зародилась более 200 лет назад в ходе решения головоломок и долго существовала независимо от науки. Как отдельная научная дисциплина теория графов появилась в 30-е годы 20в. Ее возникновение связывают с именами ЛеонардаЭйлера, венгерского математика Д. Кёнига, швейцарского ученого ОйстинаОре, которые заложили основы теории графов как математической дисциплины. Одним из основателей современной теории графов является американский математик Фрэнк Харари.

Современная наука широко использует теорию графов в различных областях. Например, теория графов находит применение в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, в частности, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Многие структуры, представляющие практический интерес в логике, информатике, математике и других науках, также могут быть представлены графами. Графы находят свое применение в теории управления и социологии, биологии и медицине, экономике и прикладной математике (топологии, комбинаторике, программировании). Примерами графов служат схемы шоссейных дорог, линий метрополитена, структурные формулы молекул, схемы и планы, показывающие различные связи между объектами без указания масштаба.

Целью данной работы является изучение и применение теории графов при решении математических задач олимпиадного уровня. Актуальность вопроса определяется тем, что теория графов не изучается на школьном уровне, но входит в число обязательных заданий математических олимпиад.  Рассмотреть все многообразие применения теории графов в одной работе не представляется возможным, поэтому объектом данного  исследования будут графы с цветными ребрами. В ходе рассмотрения данной темы нам необходимо было изучить основные методы решения задач по теории графов и ответить на вопрос о том, при каком минимальном количестве людей, среди них обязательно найдётся четверо попарно знакомых или четверо попарно незнакомых людей.

Для достижения поставленной цели потребовалось решить следующие задачи:

- проанализировать учебную и научную литературу с целью определения базовых понятий и степени изученности темы;

- освоить основные понятия теории графов;

- классифицировать типы задач по теории графов;

- выявить особенности задач по теории графов с цветными ребрами;

- научиться решать задачи олимпиадного характера по данной теме;

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

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

В процессе выполнения проекта были изучены работы норвежского математика Ойстина Оре «Графы и их применение», американского математика Френка Харари «Теория графов», а также монография Л.Ю.Березиной о применении графов, решены олимпиадные задачи на основе данной теории, а также найден ответ на вопрос о минимальном количестве людей, необходимом для того, чтобы среди них обязательно нашлась четвёрка попарно знакомых или незнакомых.

Теория графов как раздел прикладной математики

1. Из истории открытия теории графов

Основы теории графов заложил в 18 веке швейцарский ученый Леонард Эйлер, когда решал задачу о кенигсбергских мостах: издавна жители Кенигсберга задавались вопросом, можно ли пройти по семи мостам (через реку Преголя), не проходя дважды ни по одному мосту.

Решая эту задачу,  Эйлер сделал следующие выводы:

• число нечётных вершин (вершин, из которых выходит нечётное число рёбер) любого графа чётно;
• если все вершины графа чётные, то его можно нарисовать, не отрывая карандаш от бумаги, причём начать можно из любой вершины и закончите вы в той же вершине;
• если в графе ровно 2 нечётные вершины, то его также можно нарисовать, не отрывая карандаш от бумаги, но начать надо обязательно в нечётной вершине, причём закончите вы в другой нечётной вершине;
• если в графе больше 2 нечётных вершин, то его невозможно начертить таким образом.

Граф, соответствующий расположению мостов Кенигсберга, имеет 4 нечётные вершины, поэтому нельзя пройти по мостам так, как требуется в условии.

Головоломка, решенная Леонардом Эйлером, стала первым шагом на пути к теории графов и определила понятия «эйлерова цикла» и  «эйлеровой цепи». Эйлеровым называется цикл, содержащий все вершины и все ребра и проходящий по каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже называется  эйлеровым.

Первая работа по теории графов, написанная Эйлером, появилась в 1736г. Но уже в 19в. графы нашли свое применение не только в головоломках. Их стали использовать при построении схем электрических цепей. В начале 20в. графы привлекли внимание топологов и получили распространение в прикладной математике. Термин «граф» впервые появился в книге «Теория конечных и бесконечных графов» выдающегося венгерского математика Д. Кёнига в 1936г.

Изучение теории графов продолжается и сейчас. Достаточно сказать, что, согласно гипотезе Харари, сегодня есть 27 не решенных еще задач, но по мере их доказательства будут появляться новые, решение которых может растянуться на десятилетия. Так, например, произошло с задачей о четырех красках, сформулированной в 1852 году. В 1976 году было опубликовано сообщение, что американским ученым удалось доказать эту задачу, однако их доказательство, основанное на переборе значительного числа так называемых неустранимых конфигураций, очень трудоемко и его невозможно провести без использования ЭВМ. Поэтому многие по-прежнему используют слово  «гипотеза», когда говорят об этой задаче.

2. Основные понятия теории графов

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

Граф – это множество точек (вершин графа) и множество линий (рёбер графа), соединяющих все или часть этих вершин.

Графы обычно изображаются в виде геометрических фигур, где вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 1).

Рис. 1

Вершины, прилегающие к одному и тому же ребру, называются смежными.

Если ребра ориентированы, то они называются дугами (чаще всего изображаются стрелочками) и граф с такими ребрами называют ориентированным графом.

Если ребра не имеют ориентации, то граф называется неориентированным.

Петля – это ребро, начальная и конечная вершина которого совпадают.

Кратные рёбра – это рёбра, соединяющие одну и ту же пару вершин (Рис.2 ).

Рис.2

Простой граф – это граф без петель и кратных рёбер.

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

Пустым называется граф без ребер (Рис.3).

Рис. 3

Полным называется граф, в котором любые две вершины смежные. (Рис. 4,5, 6)

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

Вершины A0, An называются связанными (данным путем). ВершинуA0 называют началом, An – концом пути. Если A0 = An, то путь называют замкнутым. Число n называется длиной пути.

Маршрут – это путь, ориентацией дуг которого можно пренебречь.

Цепь – это маршрут, в котором рёбра не повторяются.

Цикл – замкнутый маршрут, являющийся цепью.

Маршрут, в котором все вершины попарно различны, называют простой цепью.

Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.

Граф называется связным, если из любой вершины можно по рёбрам «добраться» до остальных.

Дерево – это связный граф без циклов.

Например:

Рис.7

Деревья часто возникают при изображении различных иерархий.

Например, популярны генеалогические деревья.

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

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

Например:

1.Матрица инцидентности.

Это таблица с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х, y) содержит – 1 в строке, соответствующей вершине х и 1, в строке, соответствующей вершине y. Во всех остальных 0. Петлю, т.е. дугу (х, х) можно представлять иным значением в строке х, например, 2.

2. Матрица смежности.

Это таблица n×n, где n – число вершин, где bxy= 1, если существует ребро, идущее из вершины х в вершину у, и bxy= 0 в противном случае.

Составим матрицы инцидентности и смежности для следующего графа:

Рис.8

Матрица инцидентности:

Матрица смежности:

3. Решение олимпиадных задач с применением теории графов

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

Задача 1

В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?

Решение:

1. Построим граф, соответствующий стране Цифра (9 вершин городов, некоторые соединены рёбрами-дорогами)
2. Вершина 1 соединена с  2, 5, 8. (12,15,18 делятся на 3)
3. 2 соединена с 1, 4, 7.
4. 5 соединена с 1, 4, 7.
5. 8 соединена с 1, 4, 7.
6. 4 соединена с 2, 5, 8.
7. 7 соединена с 2, 5 8.
8. Вершины 3, 6, 9 соединены только между собой

Рис.9

Теперь стало ясно, что из города 1 нельзя добраться в город 9.

Задача 2

Можно ли, сделав несколько ходов конями из положения на рисунке слева, расположить их так, как показано на рисунке справа? (Выходить за пределы поля 3×3 не разрешается.) 
Решение:

1. Пронумеруем клетки доски, следующим образом:

Рис.10

2. Построим граф, в котором вершинами будут являться клетки доски 1-8, а каждое ребро будет соответствовать возможности хода коня между этими клетками (центральную клетку мы не нумеруем, так как ход коня в эту клетку невозможен). (Рис. 11)

Рис.11

3. Теперь покажем расположение коней на этом графе (Рис.12).

Рис.12

4. Таким образом, кони ходят по кругу, не меняя своей последовательности, и не могут  расположиться требуемым образом.

Что такое графы с цветными рёбрами

1. Свойства графов с цветными ребрами. Решение задач.

Если на плоскости расположены несколько точек и линии, каждая из которых соединяет пару точек, то говорят, что задан граф. Точки называются вершинами графа, а линии – его ребрами. Ребра графа могут быть окрашены в несколько цветов. Такой граф будет называться графом с цветными рёбрами. Применение графов с цветными ребрами упрощает решения некоторых задач и делает их более наглядными. Задачи раскраски ребер графа занимают важное место в теории графов. К построению раскрасок сводится целый ряд практических задач. Характерной особенностью этих задач является существование объектов, которые по каким-либо причинам не могут быть объединены в одну группу.

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

Задача 1

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

Решение:

1. Представим задачу в виде графа с цветными рёбрами, тогда люди будут вершинами графа, красное ребро будет означать, что они знакомы, синее, что незнакомы, в таком случае решение задачи сводится к нахождению треугольника с одноцветными сторонами.
2. Рассмотрим вершину 1: по принципу Дирихле из неё выходят по крайней мере 3 ребра одного цвета (пусть это будут красные рёбра) (Рис.13).

Рис.13

3. Если хотя бы одно из рёбер 23, 34, 24 окажется красным, то у нас получится треугольник с красными сторонами (Рис.13, 14, 15).

Рис.14                                                Рис.15

Рис.16

4. В противном же случае (рёбра 23, 34, 24 – синие) мы получаем треугольник с синими сторонами (Рис.17).

Рис.17

Свойство 1: В любом полном графе с шестью и более вершинами и рёбрами двух цветов всегда найдётся хотя бы один треугольник с одноцветными сторонами.

Свойство 2: Из любой вершины графа с шестью или более вершинами и ребрами двух цветов выходит, по меньшей мере, три ребра одного цвета.

Задача 2

Пять городов соединены дорогами. Известно, что если рассмотреть любые три города, то среди них обязательно найдутся два города, соединённые дорогами, и два – несоединённые.

Докажите, что

1.  каждый город соединён дорогами ровно с двумя другими;
2. вылетев из любого города, можно побывать в остальных по одному разу и вернуться в исходный.

Решение:

1. Поставим граф в соответствии с условием задачи, таким образом:

• города – вершины графа
• красное ребро означает, что города соединены дорогой.
• синее – не соединены.

2. Если из одной вершины будут выходить 3 и более рёбер одного цвета, то обязательно найдётся треугольник с одноцветными сторонами, что противоречит условию, следовательно, из любой вершины выходит по 2 красных и 2 синих ребра.
3. Рассмотрим вершину 1, из неё выходит по 2 красных и синих ребра. Пусть красными будут рёбра 12 и 15, а синими – 13 и 14. Ребро 25 не может быть красным, так как тогда будет треугольник с красными сторонами 125, следовательно, оно синее (Рис.18).

Рис.18

4. Из вершины 2 должно выходить 2 красных ребра, следовательно, одно из рёбер 23, 24 – красное. Пусть это будет ребро 23, тогда ребро 24 синее. Тогда из вершины 4 выходит два синих ребра, следовательно, оставшиеся рёбра, выходящие из этой вершины, красные (34 и 45). Рёбра 24 и 35 – синие, так как иначе получатся одноцветные треугольники 234 и 345 соответственно (Рис.19).

Рис.19

5. По построенному графу видно, что всегда можно проехать, посетив все города по одному разу, и вернуться при этом в начальный город.

Свойство 3: Если в графе с пятью вершинами и рёбрами двух цветов, нет треугольника с одноцветными сторонами, то его можно начертить в виде пятиугольника со сторонами одного цвета и диагоналями другого.

Задача 3

Семнадцать учёных переписываются друг с другом на 3 темы. Докажите, что среди учёных найдётся трое, переписывающихся между собой на одну тему.

Решение:

Каждый учёный переписывается с шестнадцатью другими и, по принципу Дирихле, по крайней мере с шестью из них на одну и ту же тему. Тогда если кто-то из этих учёных переписывается между собой на эту же тему, то эти два ученых вместе с первым переписываются на одну и ту же тему, что удовлетворяет вопросу задачи. Если же никто из них не переписывается на эту тему между собой, то у этих 6 учёных остаётся 2 темы для обсуждения, и по свойству 1 среди них найдется тройка учёных, переписывающихся на одну и ту же тему.

Свойство 4:Вполном графе с семнадцатью или более вершинами и ребрами трех цветов всегда найдется, по меньшей мере, один треугольник с одноцветными сторонами.

Исследовательская часть

При решении предыдущих задач с применением теории графов с цветными ребрами возник вопрос: при каком минимальном количестве людей среди них обязательно найдётся четверо попарно знакомых или попарно незнакомых?

Чтобы ответить на данный вопрос,рассмотрим задачу.

Задача 4

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

Решение:

Рассмотрим граф, соответствующий условию задачи.

Красное ребро – незнакомы.

Синее ребро – знакомы.

Из 1 вершины по принципу Дирихлевыходит по крайней мере 4 ребра одного цвета. Рассмотрим 2 случая:

1. Из 1 вершины выходит ровно 4 ребра одного цвета, тогда рёбер другого цвета тоже 4. Для удобства расположим их следующим образом:

Рис.20

Но тогда, если хотя бы одно из рёбер 67, 68, 69, 78, 79, 89 будет синим, то найдётся треугольник с синими сторонами, если же все они будут красными, то найдётся четырёхугольник с красными сторонами.

2. Из вершины 1 выходит больше 4 рёбер одного цвета, тогда

• если это будут синие рёбра (для удобства возьмём 12, 13, 14, 15, 16), тогда если хотя бы одно из рёбер 23, 24, 25, 26, 34, 35, 36, 45, 46, 56 будет синим, то найдётся треугольник с синими сторонами, если же все эти рёбра будут красными, то найдётся четырёхугольник с красными сторонами;
• если это будут красные рёбра (для удобства возьмём 12, 13, 14, 15, 16), (Рис.21)

Рис.21

то в подграфе 23456 возможны 2 варианта:

• найдётся треугольник с одноцветными сторонами. Если он будет синим, то задача решена; если он будет красным, например 234, то найдётся четырёхугольник с красными сторонами (1234);
• треугольника с одноцветными сторонами не будет, тогда по свойству 2 подграф 23456 можно начертить как пятиугольник со сторонами одного цвета и диагоналями другого (пусть диагонали будут синие, а стороны – красные), тогда найдётся четырёхугольник с красными сторонами, например 1234. (Рис.22)

Рис.22

Попробуем определить,  сколько вершин должно быть у графа, чтобы всегда нашелся четырёхугольник с одноцветными сторонами. (Или сколько людей должно встретиться, чтобы среди них нашлось или четверо попарно знакомых, или четверо попарно незнакомых)?

Решение:

Число вершин данного графа больше 17, так как для графа с 17 вершинами возможна раскраска, не удовлетворяющая условию задачи (Рис. 23).

Рис.23

Теперь докажем, что в графе с 18 рёбрами всегда найдётся четырёхугольник с одноцветными сторонами:

Рассмотрим вершину 1, из которой по принципу Дирихле выходят по крайней мере 9 рёбер одного цвета (пусть это будут синие рёбра) (Рис. 24).

Рис. 24

А при решении предыдущей задачи мы выяснили, что в графе с 9 вершинами (2 3 4 5 6 7 8 9 10) всегда найдется одноцветный четырёхугольник или треугольник:

1. Найдётся красный четырёхугольник или синий треугольник:

а) если найдется красный четырехугольник, то задача решена;

б) если найдется синий треугольник, то задача также доказана, так как все вершины этого треугольника соединены синими рёбрами с вершиной 1. Следовательно, мы получили четырёхугольник с синими сторонами;

2. Найдётся синий четырёхугольник или красный треугольник:

а) если найдется синий четырехугольник, то задача решена;

б) если найдётся красный треугольник (пусть для определенности 234), то в шестиугольнике 5 6 7 8 9 10 обязательно найдётся одноцветный треугольник, если он синий, то задача решена, так как вершины данного треугольника соединены также синими рёбрами с вершиной 1, если же он будет красным (для определённости возьмём 5 6 7), то мы рассмотрим шестиугольник 234567:

Рис. 26

Если среди рёбер  25, 26, 27, 35, 36, 37, 45, 46, 47 нет красных, то найдётся четырёхугольник с синими  сторонами (например 1256)

Рис. 27

Если красные  рёбра есть, тогда (для определённости) красное ребро 25, тогда рёбра 36, 37 – синие, чтобы избежать четырёхугольника с красными сторонами (2356 или 2357), но если они синие, то получаем синий четырёхугольник 1367.

Рис. 28

3. Числа Рамсея

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

Эти числа обозначаются R (a, b), где a и b – это количество вершин многоугольников с одноцветными сторонами. По ходу решения задач мы доказали, что:

R (3,3) = 6 – из задачи о шести случайно выбранных людях;

R (3,4) =9 –  из задачи о вечеринке;

R (4,4) =18 – из последней задачи.

Существует теория, выведенная Фрэнком Рамсеем в 1928 году и использованная им для доказательства тезиса, выдвинутого Бертраном Расселом и Альфредом Нортом Уайтхедом: «все математические истины могут быть выведены из ограниченного набора аксиом» в специальном случае (позже было доказано, что в общем случае это неверно). Однако Ф.Рамсей не смог продолжить свои исследования, так как в 1930 году он заболел и в возрасте двадцати шести лет умер от осложнений после операции.

До 1933 года никакие исследования, связанные с теорией Ф.Рамсея, не проводились. А в 1933г. венгерские математики Пауль Эрдёш и Джордж Шекереш заново её открыли. Они решали задачу, предложенную им студенткой Эстер Клейн, о нахождении на плоскости выпуклого четырёхугольника (для этого требуется пять точек, никакие три из которых не лежат на одной прямой).

Они заинтересовались этой темой и, быстро обобщив данную задачу, доказали, что среди девяти точек всегда найдётся выпуклый пятиугольник. Д.Шекереш показал, что если число исходных точек достаточно велико, то всегда найдётся необходимая подструктура, и тем самым заново открыл теорию Рамсея, хотя и не догадывался об этом. П. Эрдёш выдвинул гипотезу, что количества точек n=1+2k-2 достаточно для того, чтобы нашелся многоугольник с k- сторонами. Однако эта гипотеза не доказана до сих пор.

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

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

Таким образом, усилиями Ф.Рамсея, П.Эрдёша и многих других были заложены основы теории, носящей имя Рамсея. Пока что исследователи только начали изучать следствия этой теории. Она позволяет предположить, что структурная основа математики состоит из чрезвычайно больших чисел и множеств – объектов столь громадных, что их трудно даже выразить, а тем более постичь.

Заключение

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

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

В данной проектной работе были рассмотрены основные теоретические положения, связанные с теорией графов, показаны примеры решения задач, а также рассмотрена задача, в результате решения которой было найдено число Рамсея (3;4) и число Рамсея (4;4).

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

Библиография

1. Березина Л.Ю. Графы и их применение. Пособие для учителя. – М: Просвещение, 1979.
2. Березина Л.Ю. Графы с цветными ребрами. – «Квант», 1996, №6.
3. Оре О. Графы и их применение. Серия «Современная математика». – М: «Мир», 2008.
4. Харари Ф. Теория графов. Под ред. Г.П.Гаврилова. – М: «Мир», 2003.
5. Интернет-источники:

Википедия. [Электронный ресурс] /http://ru.wikipedia.org/

Google. [Электронный ресурс] /http://www.google.ru/

Олимп. Задачи откуда