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

В математике существует специальный раздел, который называется «Теория графов».

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

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

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

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

1 Граф Эйлера

Родилась теория графов в Санкт-Петербурге. Ее создателем является Л. Эйлер, который в 1736 году опубликовал решение задачи о Кенигсбергских мостах.

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

Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис. 1], на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера.

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

В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Таким образом, сформулируем правило Эйлера.

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

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

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

Доказательство правила Эйлера звучит следующим образом:

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

2 Дальнейшая разработка теории графов.

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

А вместо этого он предложил простую , но эффективную методику (ставшую позднее стандартной процедурой), в соответствие с которой достаточно ограничиться только независимыми простыми циклами графа, определяемыми любым из его “остовных дервьев”. На рисунке дан пример электрической цепи N, соответствующего ей графа G и остовного дерева T.

Кэлли в 1857 году, занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемый деревьями. Он стремился перечислить изомеры предельных (насыщенных) углеводородов с данным числом n атомов углерода.

Конечно, Кэлли, прежде всего, сформулировал задачу абстрактно: найти число всех деревьев с p вершинами, каждое из которых имеет вершины со степенями 1 и 4. Ему не удалось сразу решить эту задачу, и он стал изменять ее формулировку таким образом, чтобы можно было решить новую задачу о перечислении: а) корневых деревьев (в которых выделена одна из вершин); б) всех деревьев; в) деревьев, у которых степени вершин не превышают четырех; г) деревьев, у которых степени вершин равны 1 и 4 (постановка задачи “из химии”).

Позже, Жордан (1869 год), независимо от Кэлли, ввел и изучал деревья как чисто математические объекты, и, как писал Сильвестр в 1882 году, он сделал это, “совершенно не подозревая о значении своего открытия для современной химической науки”.

В 1859 году сэр Вильям Гамильтон придумал игру “Вокруг Света”. В ней используется додекаэдр, каждой из двадцати вершин которого приписано название известного города. Играющий должен обойти “вокруг света”, найдя такой замкнутый путь, идущий по ребрам многогранника, который проходил бы через каждую вершину рово один раз. Гамильтон продал свою идею одному мастеру игрушек за 25 гиней; это был жестокий поступок, ибо описанная игра не сулит никакой финансовой удачи. На языке теории графов задач формулируется так: найти остовный цикл в графе додекаэдра.

Вершины графа пронумерованы числами 1, 2,,20 (вместо названий городов). Существование остовного цикла очевидно.

Гипотеза Четырех красок имеет интересную историю, но в ее появлении имеется много непонятного. Формулировка задачи и исторической статьи Мея: “Предполагается, что любую карту на плоскости или поверхности шара можно раскрасить только четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Каждая страна должна состоять из одной связной области, а смежными называются страны, которые имеют общую границу в виде линии (а не в виде одной общей точки. ) В 1852 году Френсис Гутри, составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану, а тот- математической общественности.

Первое доказательство появилось год спустя и принадлежало В. Кемпе. Одиннадцать лет спустя П. Хивуд обнаружил в нем ошибку. (Однако из доказательства Хивуд понял, что пяти красок действительно недостаточно. Тем не менее для любой конкретной карты хватало четырех красок!) За первым ошибочным доказательством последовало множество других. В этом отношении проблема четырех красок уступала лишь знаменитой прблеме Ферма. До середины ХХ века, хотя проблемой четырех красок занимались выдающиеся математики, положение с доказательством изменилось несущественно: идеи Дж. Биркгофа позволили П. Франклину в 1913 году доказать гипотезу для карты с не более чем 25 странами. Позже это число было увелчено до 38.

В 1977 году доказательство гипотезы четырех красок было наконец получено К. Аппелем и У. Хакеном. Значительную часть рутинных проверок выполнил компьютер, и это революционное нововведение в сложившуюся практику дедуктивных рассуждений в чистой математике служит основанием для некоторого естественного скептицизма по отношению к данному доказательству и по сей день. Вот что говорят сами авторы доказательства: “Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно. ” Говоря прямо, компьютерную часть доказательства невозможно проверить вручную, а традиционная часть доказательства длинна и сложна настолько, что ее никто целиком и не проверял. Именно поэтому некоторые математики отнеслись к этому доказательству с недоверием. Проблема четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

В 1936 году психолог Левин высказал предположение, что “жизненное пространство” индивидуума можно представить с помощью планарной карты. На такой карте области представляют разлиные типы деятельности человека, например, то, что он делает на работе, дома, или же его хобби.

Подчеркнем, что Левин фактически имел дело с графами, как это следует из рисунка Х. Эта точка зрения привела психологов Научно-исследовательского центра групповой динамики к другой психологической интерпретации графа, в которой люди представляются вершинами, а их отношения- ребрами. Такими отношениями являются, например, любовь, ненависть, общение, подчинение.

Физики-теоретики, для внутренних нужд своей науки, “открывали” теорию графов не один раз. Занимаясь статистической механикой, Уленбек обозначал точками (вершинами) молекулы, а смежность вершин толковал как взаимодействие наибольшей близости (соседства) некоторого физического типа, например, магнитное притяжение или отталкивание. В подобной интерпретации, предложенной Ли и Янгом, вершинами служат малые кубы, лежащие в евклидовом пространстве; каждый куб может быть занят или нет молекулой. Две вершины считаются смежными, если оба соответствующих куба заняты молекулами.

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

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

Теоретико-графовый подход использовался в разделах линейного программирования и исследования операций при изучении потоков в сетях в работах, как Форда, Фалкерсона, Вайды, Бержа, Гуйя-Ури. Вершинам графа соответствуют пункты размещения (или выгрузки) товара; ориентированное ребро, идущее из одной вершины в другую, указывает на возможность транспортировки товара из пункта, соответствующего первой вершине, в пункт, соответствующий второй вершине. Каждому ребру приписывается некоторое положительное число- пропускная способность ребра. Она показывает, какое максимальное количество товара может быть выгружено в единицу времени в соответствующем пункте.

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

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

1 2. 1. Терминология теории графов.

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

V - множество вершин или узлов,

E -множество пар вершин, называемых рёбрами.

V (а значит и E) обычно считаются конечными множествами. Многие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.

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

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

Цепью называется последовательность ребер.

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

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом.

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

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

Степенью вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

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

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

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

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

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

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

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 3 (вытекает из рассмотренной нами теоремы).

Невозможно начертить граф с нечетным числом нечетных вершин.

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

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

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

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

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

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

2 2. 2. Графы ориентированные и неориентированные.

Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:

-V это множество вершин или узлов,

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

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w.

Путем в графе называется такая последовательность дуг) u= (, в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь u, последовательными вершинами которого являются вершины а, b, m, обозначается через u=(a,b,m). Длиной пути u= () называется число l (u ) =k, равное числу дуг, составляющих путь u. Путь может быть бесконечным и конечным. В случае бесконечного пути l(u)= ∞. Путь, в котором никакая дуга не встречается дважды, называется простым. Путь, в котором никакая вершина не встречается дважды, называется элементарным.

Контур- это конечный путь u= (, у которого начальная вершина совпадает с конечной. При этом контур называется элементарным, если все его вершины различны (за исклчением начальной и конечной, которые совпадают). Контур единичной длины, образованный дугой вида (а,а), называется петлей.

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

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

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

Важным частным случаем неориентированного графа является дерево.

3 2. 3. Деревья

Деревом называется конечный связный неориентированный граф, не имеющий циклов.

Если дано множество вершин, a, b, с , то дерево можно построить следующим образом. Одну из вершин, например а, примем за начальную и назовем ее корнем дерева. Из этой вершины проведем ребра в близлежащие вершины b, c, d,, из них проведем ребра в соседние с ними вершины e, f, g, h и. т. д. Таким образом, дерево можно построить, последовательно добавляя ребра в его вершинах. Это дает возможность установить связь между числом вершин и числом ребер дерева.

Простейшее дерево состоит из двух вершин, соединенных ребром. Каждый раз, когда мы добавляем еще одно ребро, в конце его прибавляется также и вершина. Следовательно, дерево с n вершинами имеет n-1 ребро.

Свойство 1.

Для каждой пары вершин дерева существует единственный путь, их соединяющий.

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

Свойство 2.

Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

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

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

Лес (или ациклический граф) - неограф без циклов (может быть и несвязным).

Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:

G - дерево;

G - связный граф, содержащий n-1 ребро;

G - ациклический граф, содержащий n-1 ребро;

Любые две несовпадающие вершины графа G соединяет единственная цепь.

G - ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.

Остов (каркас) связного графа - дерево, содержащее все вершины графа. Определяется неоднозначно.

Редукция графа - остов с наибольшим числом ребер.

Цикломатическое (или циклический ранг) число графа ν=m-n+c, где n - число вершин,m - число ребер, c - число компонент связности графа.

Коциклический ранг (или коранг) ν*=n-c.

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

Неограф G является лесом тогда и только тогда, когда ν(G)=0.

Неограф G имеет единственный цикл тогда и только тогда, когда ν(G)=1.

Остов неографа имеет ν* ребер.

Ребра графа, не входящие в остов, называются хордами.

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

Практическое применение теории графов

1 3. 1 Прикладные типовые задачи теории графов

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

Задача о наименьшем расстоянии может быть сформулирована следующим образом:

Пусть задана сеть из n + 1 вер- шины, то есть ориентированный граф, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Дли- ной пути (контура) называется сумма длин входящих в него дуг

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

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

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

1) конечной вершине приписывается индекс 0;

2) всем аершинам, из которых идет ребро в конечную вершину приписывается индекс 1;

3) всем вершинам, еще не имеющим индексов, из которых ребро идет в вершину с индексом , приписывается индекс +1.

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

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

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

Задача поиска контура минимальной длины решается следующим образом. Если известно, что искомый контур содержит некоторую вершину, то нужно определить кратчайшей путь от этой вершины до нее же, применяя описанные выше алгоритмы. Так как в общем случае контур минимальной длины может проходить через любую вершину графа, то находятся контуры минимальной длины, проходящие через каждую вершину, и среди них выбирается кратчайший. Более простым является следующий алгоритм 4: берется первая вершина (в произвольном их упорядочении) графа и рассматривается сеть, в которой эта вершина является одновременно конечной и начальной вершиной. Для этой сети (применением описанного выше алгоритма) ищется путь m1 минимальной длины L(m1). Затем первая вершина отбрасывается, и минимальный путь m2 ищется для сети, в которой начальной и конечной вершиной является вторая вершина. Затем отбрасывается вторая вершина и т. д. для всех вершин исходного графа, для которых существует контур, проходящий через них и через вершины с большими номерами. Контуром минимальной длины будет контур mmin, длина которого равна L(mmin) = min {L(m1), L(m2), ,. , L(mn)}.

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

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

2 3. 2. Моя прикладная задача

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

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

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

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

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

Установим зависимость между количеством ребер и вершин в графе.

Удалив висячую вершину из дерева G вместе с ребром, получим новый граф. Этот граф будет так же связным, и в нем будут отсутствовать циклы, то есть граф - тоже дерево. Из графа , удалив вершину вместе с выходящим из нее ребром, можно получить дерево , и так далее. Выполнив описанные операции, мы получим последовательность деревьев, которая оканчивается деревом, состоящим из одной вершины и не имеющим ребер. Для этого дерева выполняется соотношение m= n-1, где n – число вершин графа, а m- число его ребер. Теперь будем добавлять в обратном порядке удаленные ранее вершины и ребра. При каждом возвращении добавляется одна вершина и одно ребро, при этом равенство m= n-1 сохраняется.

Следовательно, мы доказали, что в любом дереве число ребер на единицу меньше числа вершин.

Вернемся к поставленной задаче - расстановке дежурных в школе. Поскольку мы установили, что наш граф имеет 8 вершин (главных постов дежурства), то дерево G будет иметь 8 вершин и 7 ребер. При этом две вершины, соответствующие постам на парадном входе и главной лестнице, требуют двух дежурных, остальные - по одному. Всего необходимо 22 + 61 + 7 3= 4+6+21= 31 ученик, что вполне соответствует среднему количеству учащихся в классе.

Заключение.

Теория графов - это исключительно важный и потому активно развивающийся раздел в математике. Глубокая идея, лежащая в основе теории, состоит в том, что мощный аппарат теории графов существенно помогает в решении многих практических задач. Теория графов родилась при решении головоломок и игр (задача о Кёнигсберских мостах) и стала мощным средством исследования и решения многих задач, возникающих при решении больших, сложных систем. Сразу после возникновения теории графов стало ясно, что она имеет не только огромную теоретическую ценность, но также и массу практических приложений. Теория графов используется не только в математике, но и в информатике, химии, экономике,для учета затрат, логистике, схемотехнике, в коммуникационных и транспортных системах( в частности, для маршрутизации данных в Интернете). Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computer science). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т. д.

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

Сейчас роль теории графов несомненна.