Применение теории графов для решения задач

Титульник 

Оглавление

 

Введение 3

Элементы  теории графов. 5

Применение  теории графов для решения задач. 15

Заключение 29

Литература 30

 

 

Введение

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

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

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

Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

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

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

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

 

 

 

 

Элементы теории графов.

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

Вершины графа изображаются в виде точек на плоскости. Если две вершины образуют ребро, то соответствующую пару точек соединяют линией. Вершины графа обозначают латинскими буквами A, B, C, D или цифрами. Иногда граф в целом можно обозначать одной заглавной буквой.

Рис. 1

Например, на рис. 1 изображен граф G, заданный множеством вершин

F = {1,2,3,4,5} и множеством ребер Е = {(1,2), (2,3), (4, 2), (4,3)}.

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

Вершины, которые соединены ребром, называются его концами. Если вершина является концом ребра, то будем говорить, что ребро выходит из вершины. Число ребер, выходящих из вершины v, называется степенью вершины v и обозначается d(v). Для графа, изображенного на рис. 1, d(1) = 1, d(2) = 3, d(3) = 2, d(4) = 2, d(5) = 0. Вершина степени 0 называется изолированной, вершина степени 1 — висячей.

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

Рис. 2

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

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

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

Пусть граф G имеет п вершин и т ребер. Сложив степени вершин графа G d(1), d(2),..., d(n), мы получим сумму, в которую каждое ребро входит дважды, поскольку каждое ребро вносит по единице в степень ровно двух вершин. Поэтому d(l) + d(2) + ... + d(n) = 2m.

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

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

Действительно, если предположить противное, то сумма степеней вершин графа окажется нечетным числом, что противоречит теореме 1.

Теорема 2. В простом графе найдется не менее двух вершин с одинаковыми степенями.

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

Докажем это утверждение от противного. Допустим, что существует граф Н, степени  всех n вершин которого различны.

В промежутке от 0 до n - 1 существует ровно n целых чисел: 0,1,2,..., n - 2, n - 1. С другой стороны, степени n вершин графа тоже расположены в этом промежутке. Поэтому должны существовать такие вершины v₁, v₂,..., v_n, что d(v₁) = 0, d(v₂) = 1, ..., d(v_n) = n - 1.

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

Теорема 3. В простом графе с n вершинами число ребер не больше .

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

Всего n вершин, каждая из них может быть соединена не более чем с (n-1) остальными вершинами. Таким образом, получаем (n-1)n ребер, но каждое из них посчитано ровно два раза, так как соединяет две вершины. Поэтому делим полученное выражение пополам. Теорема доказана.

Граф называется полным, если каждая его вершина соединена со всеми другими вершинами графа. Полный граф с n вершинами обозначается К_n. Граф К_n содержит ребер.

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

Граф Н называется подграфом графа G, если вершины и ребра Н принадлежат G. Подграф Н графа G называется подграфом, порожденным множеством вершин {v₁, v₂,..., v_p}, если он содержит вершины v₁, v₂,..., v_p и все ребра графа G, соединяющие эти вершины.

Рис. 3

Подграф Н графа G называется подграфом, порожденным множеством ребер {e₁, e₂,..., е_s}, если он содержит ребра e₁, e₂,..., е_s и все вершины графа G, являющиеся концами этих ребер.

На рис.3 изображен граф G и два его подграфа Н₁ и Н₂, причем подграф Н₂ порожден множеством вершин {1, 2, 4, 5} или множеством ребер {(1, 2), (1, 4), (2,4), (2, 5), (4, 5)}.

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

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

Рис. 4

Маршрутом в графе называется такая последовательность чередующихся вершин v_i и ребер e_j графа (v₀, e₀, v_l, e_1, v₂,... ,e_k-1, v_k), что каждое ребро соединяет вершины последовательности, между которыми оно находится, т.е. ребро e_i соединяет вершины v_i и v_i+1.

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

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

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

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

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

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

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

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

Рис. 5

Полный двудольный граф, доли которого состоят из р и q вершин, обозначается K_p,q. На рис.5 изображены некоторые полные двудольные графы.

Полный двудольный граф K_p,q имеет ребер.

Теорема о сумме  степеней вершин двудольного графа. Суммы степеней вершин долей двудольного графа равны.

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

 Пусть v₁,v₂, …v_k — вершины одной доли, а u₁, u₂,...,u_p — вершины другой доли. Тогда из одной доли выходит d(v₁) + d(v₂) + …+d(v_k) ребер,а из другой — d(u₁) + d(u₂) + ... + d(u_p) ребер. Равенство сумм следует из того, что это одни и те же ребра. Теорема доказана. 

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

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

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

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

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

Объединим циклы Р₁ и Р₂ следующим образом: пройдем часть Р₁ от вершины v₁ до вершины v₂, затем пройдем цикл Р₂, затем — оставшуюся часть Р₁ от v₂ до v₁ (см. рис. 6).

Рис. 6

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

Цепь в графе, содержащая каждое его ребро, называется эйлеровой цепью.

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

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

 Очевидно, что никакая вершина нечетной степени не может принадлежать эйлеровой цепи, если только она не является его концом.

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

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

Важным частным случаем  графа является дерево.  Это название связано с типичным видом некоторых  представителей данного класса.

Деревом называется связный граф, не содержащий  циклов. Несвязный граф, не имеющий циклов, называют лесом. Пример дерева приведен на рис. 7.

Рис. 7

Теорема 6. В любом дереве есть хотя бы одна висячая вершина.

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

Предположим противное, то есть предположим, что в дереве нет вершин степени единица. Рассмотрим дерево G и его произвольную вершину v₁.Перейдем из нее по любому ребру (v₁, v₂) в вершину v₂. Поскольку степень вершины v₂ не меньше двух, то из нее по новому ребру можно перейти в вершину v₃ и т. д. Но число вершин в дереве G конечно. Поэтому, в конце концов, мы придем в одну из тех вершин, в которых были раньше (см. рис.8).

Рис. 8

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