VII Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Теория Графов

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Куванова М.А. 1Пивоваров В.А. 2

---

1МАОУ "Гимназия №1"

2МАОУ "Гиназия№1"

Дятел О.И. 1

---

1МАОУ "Гимназия №1"

Работа в формате PDF

1 MB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

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

Актуальность: Графы заинтересовали меня своей возможностью помогать в решении различных головоломок, математических и логических задач. Теория графов в настоящее время является интенсивно развивающимся разделом дискретной математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химические молекулы, отношения между людьми, всевозможные транспортные схемы и многое-многое другое. ( Приложение 1 ) Очень важное, для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Я решила разобраться, какую роль в обычной жизни играют графы.

Объект исследования: понятие граф

Предмет исследования: степень распространенности применения графов

Цель исследования: Исследовать роль графов в нашей жизни.

Задачи исследования:

1.познакомиться с историей возникновения графов;

2.познакомиться с основными понятиями графа, видами, элементами;

3.научиться решать задачи с помощью графов;

4.составить своё родословное дерево.

Методы исследования: поисковый, аналитический.

ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Проблема семи мостов Кёнигсберга – старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений можно сделать следующие выводы:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

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

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

 →   → 

Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных в Интернете).

ТЕРМИНОЛОГИЯ ТЕОРИИ ГРАФОВ

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

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

Неориентированный граф  — это упорядоченная пара ,

где  — это непустое множество вершин или узлов, а  — множество пар неупорядоченных вершин, называемых рёбрами.

  и (иначе оно было бы мультимножеством¹) обычно считаются конечными множествами.

Ориентированный граф (орграф)  — это упорядоченная пара,

где  — непустое множество вершин или узлов, и  — множество (упорядоченных) пар различных рёбер, называемых дугами или ориентированными рёбрами.

Смешанный граф  — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой , где , и   определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями смешанного.

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

Петля – ребро, концы которого совпадают.

Маршрут  – конечная последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром.

Цепь - маршрут без повторяющихся рёбер. 

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

Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов². В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств. G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

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

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

СТЕПЕНЬ ВЕРШИНЫ (ТЕОРИЯ ГРАФОВ)

Степени вершин и подсчет числа ребер.

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

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

Рисунок 1

На рисунке 1 изображен граф с пятью вершинами.

Степень вершины А обозначим Ст.А.
На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Доказательство:

Эта закономерность очевидна уже после рассмотрения любого полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n—1 ребро, что и требовалось доказать.

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

Доказательство:

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

АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ С ПОМОЩЬЮ ГРАФОВ

Нарисовать граф

Определить степень каждой вершины и подписать возле нее.

Посчитать количество нечетных вершин.

Обход возможен:

ЕСЛИ все вершины – четные, и его можно начать с любого участка.

ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей.

Обход невозможен, если нечетных вершин больше 2.

Сделать ВЫВОД.

Указать Начало и Конец пути.

ТРАНСПОРТНЫЕ СЕТИ

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

ЗАДАЧИ, ПРИВОДЯЩИЕ К ТРАНСПОРТНЫМ СЕТЯМ

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

Для распределения дополнительного потока машин необходимо знать пропускную способность каждой улицы, т.е. число машин, которые одновременно могут проехать через «поперечное сечение улицы» за единицу времени. На рисунке 2 над ребрами поставлены числа, указывающие на пропускную способность соответствующих улиц. Здесь пропускная способность ребра <B₀; B₁> равна 3, а ребра <В_1; В₂> равна 4. Это означает, что наибольшее число машин, пропускаемых путем <В₀; В₁> в единицу времени, равно 3, а путем <B₁;B₂> - равно 4.

При заданных условиях требуется определить максимальное значение потока в сети улиц, а в конкретном случае – наибольшее число машин, которое может пропустить сеть улиц в единицу времени от В₀ к Вn.

Для решения этой задачи подсчитаем сначала, сколько машин (в единицу времени) могут пропустить улицы, выходящие из В₀. Для этого условно рассечем их поперек (рис.3) и найдем сумму их пропускных способностей: 3+4+5=12

Все ли машины за единицу времени может принять В_n? Нет, не все, так как только 2+6+1=9 машин могут пройти (за единицу времени) по улицам, входящим в В_n (рис.4). Напоминаем, что мы рассматриваем только непрерывные потоки.

Но оказывается, что и 9 машин не могут быть пропущены ( единицу времени) через улицы города, поскольку пропускные способности улиц города для этого недостаточны. Чтобы убедиться в этом, снова рассмотрим поперечное сечение улиц города, проводящих транспорт от В₀ к В_n, например, такой, который выделен на рисунке 4 двойной штриховой линией, и найдем сумму их 2+1+3+1+1=8.

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

Докажем, что 8 машин одновременно смогут пройти через любое поперечное сечение улиц города. Для этого распределим 8 машин по улицам, учитывая их пропускную способность. Один из вариантов распределения такого потока представлен на рисунке 5. Число машин, пропускаемых одновременно через поперечное сечение их пропускной способности. (Найдите для этой сети другое распределение по ребрам потока значением 8).

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

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

Задача о максимальном значении потока в сети.

Определить максимальное значение потока, который может пропустить транспортная сеть из пункта отправления В₀ в пункт назначения В_n, если известна пропускная способность каждого ребра.

Рассмотрим экономическую задачу, которую можно описать и решить с помощь сетей.

Пусть в какой-то области есть две мебельные фабрики Ф₁ и Ф₂, которые снабжают мебелью три магазина – М₁, М₂, М₃. Нас будут интересовать только книжные шкафы. В начале месяца каждый из магазинов делает заявку на определенное число книжных шкафов, т.е. заказывает столько шкафов, сколько предполагает продать в течение месяца. Это позволяет установить общее число книжных шкафов, которые требуется изготовить на этих двух фабриках.

Пусть магазину М₁ требуется 10 шкафов, магазину М₂ – 8, магазину М₃ - 7, т.е. всего 25 книжных шкафов. Пусть на фабрике Ф₁ изготовлено 11 шкафов, на фабрике Ф₂ – 14 (рис.6). Известна стоимость с_ij перевозки одного шкафа по каждому из путей от фабрики Ф_i до магазина М_j. Так, с₁₁ = 80к., с₁₂ = 60 к., с₁₃ = 1 р., с₂₁ = 90 к., с₂₂ =50 к., с₂₃ = 70к. Поставим эти цены над соответствующими ребрами(рис.7). Требуется определить, сколько шкафов следует отправить с каждой фабрики в каждый из магазинов, чтобы общая стоимость всех перевозок была минимальной.

Для решения задачи, естественно, попытаемся перевезти наибольшее число шкафов по путям с наименьшей стоимостью. В магазин М₁ доставим все 10 шкафов с фабрики Ф₁, избежав транспортировки по пути Ф₂М_1. В магазин М₃ доставим все 7 шкафов с фабрики Ф_2, избежав путиФ₁М₃. Тогда в М₁ остается привезти 7 шкафов из одной фабрики и один из другой (рис.8). Общее число шкафов полученных первым магазином, 10+0=10, вторым магазином, 1+7=8, третьим магазином, 0+7=7. Подсчитаем общую стоимость перевозки: (80×10 + 60×1 + 100×0) + (90×0 + 50×7+ 70×7) = 1700 к. или 17 р.

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

Задача о потоке минимальной стоимости.

В транспортной сети требуется так распределить заданное количество товаров по путям, чтобы общая стоимость транспортировки была бы минимальной. Предполагая известным количество товара, который необходимо переправить по сети из В₀ вВ_n, стоимость перевозки едины товара по каждому участку (ребру), пропускная способность каждого пути.

ОСНОВНЫЕ ПОНЯТИЯ

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

Число, которое приписывается ребру, называется пропускной способностью ребра.

Сеть, в которой только один источник и один исток, называется транспортной сетью. Ее обозначают буквой Т.

Потоком в транспортной сети Т называется функция f(T).

РЕШЕНИЕ ЗАДАЧ

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

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

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

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

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

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

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Степени вершин и подсчет числа ребер графа

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

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

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

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

Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

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

Графы Эйлера

Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

Задача 8.

Задача.

В углах шахматной доски 3х3 стоят 4 коня: 2 белых (в соседних углах) и два черных. Можно ли за несколько ходов (по шахматным правилам) поставить коней так, чтобы во всех соседних углах стояли кони разного цвета?

Решение.

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

Задача 9.

Задача.

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

Решение:

Задача решается с помощью связных графов. Встретились пятеро:

В результате имеем 10 ребер в графе, значит, возможно 10 рукопожатий.

Задача 10.

Задача

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

Для решения используем ориентировочный плоский граф

Получаем 6 ребер и 12 стрелок, значит, передано 12 визитных карточек.

Задача 11.

Задача

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

Нарисуем граф-дерево

Сочетания: х-р, х-а, х-г, к-р, к-а, к-г Итого: 6 сочетаний.

Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Решение. Занумеруем клетки доски, как показано на рисунке:

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

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

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

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Степени вершин и подсчет числа ребер.

3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих городов дорог – 100 ^. 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?

Ответ. Нет (теорема о четности числа нечетных вершин).

5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ. Нет, не может.

6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

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

Связность.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

Применение теории графов:

В химии (для описания структур, путей сложных реакций^[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров углеводородов и других органических соединений.

В информатике и программировании (граф-схема алгоритма)

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

В экономике

В логистике

В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).

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

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

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

ЛИТЕРАТУРА

Т. Варга Математика 2. Плоскость и пространство. Деревья и графы. Комбинаторика и вероятность: (Математические игры и опыты). Пер. с нем. – М.: Педагогика, 1978.– 112 с. с ил.

Л. Ю. Березина Графы и их применение: Пособие для учителей. – М.: Просвещение, 1979. – 143 с. с ил.

А. Г. Ванцян Математика: Учеб для 5 кл. - Самара, «Федоров», 1999.

Приложение 1.