WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 7 |
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ В.Н. Берцун МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ Часть 1 Учебное пособие Томск – 2006 2 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1 УДК 519.17 ББК 22.174 Б 527 Берцун В.Н. Математическое моделирование на графах.

Б 527 Часть 1: Учебное пособие. – Томск: Изд-во НТЛ, 2006. – 88 с.

ISBN 5-89503-312-1 Учебное пособие предназначено для студентов механико-математических и физико-математических факультетов университетов. Оно также может быть полезно студентам других специальностей и аспирантам, занимающимся математическим моделированием прикладных задач и оптимизацией вычислительных алгоритмов для высокопроизводительных компьютеров (кластеров).

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

УДК 519.17 ББК 22.174 Рецензент:

доктор физико-математических наук А.В. Старченко ISBN 5-89503-312-1 © В.Н. Берцун, 2006 © Томский госуниверситет, 2006 Глава 1. Основные понятия теории графов 3 СОДЕРЖАНИЕ ВВЕДЕНИЕ..............................................................................................4 Гл а в а 1. Основные понятия теории графов.................................5 1.1. Из истории теории графов..........................................5 1.2. Граф и его дополнение................................................6 1.3. Маршрут в графе, цикл, связанность.......................12 1.4. Компоненты связности графа...................................16 1.5. Изоморфизм графов...................................................18 1.6. Двудольные графы и их свойства.............................20 1.7. Ориентированные графы...........................................23 1.8. Деревья и их свойства...............................................28 1.9. Ациклические графы.................................................Задачи.................................................................................Гл а в а 2. Плоские и планарные графы........................................2.1. Свойства плоского графа...........................................2.2. Эйлеровы графы.........................................................2.3. Гамильтоновы графы.................................................2.4. Гиперкуб и его свойства............................................2.5. Графы сеточных функций.........................................Задачи.................................................................................ЛИТЕРАТУРА.........................................................................................БИОГРАФИЧЕСКИЙ УКАЗАТЕЛЬ.....................................................4 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть ВВЕДЕНИЕ В настоящее время компьютерное моделирование резко расширило сферу своего применения в различных областях знаний. Это относится и к теории графов – разделу прикладной математики, который нашёл своё применение: в теории игр и квантовой химии, экономике и политике, логистике и социологии, биологии и медицине, оптимальном управлении и навигации, создании сложных программных комплексов и анализе современных компьютерных систем на основе сетей Петри [1 – 7]. Свойства графов активно используются и для решения краевых задач на сетевых системах (нефтепроводах, газопроводах, электросетях и т.д.), в решении сложных задач на многопроцессорных вычислительных системах (МВС).

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

Глава 1. Основные понятия теории графов Глава ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ 1.1. Из истории теории графов Теория графов как математическая дисциплина стала активно развиваться еще со времен Эйлера (1707 – 1783 гг.), который в 1736 г.

решил задачу о Кёнигсбергских мостах [2]. В городе два острова, соединенные семью мостами (см. рис. 1.1). Можно ли побывать на всех четырёх частях суши, пройдя по каждому мосту один раз и оказаться на той части суши, с которой началось движение C L A B Рис. 1.Термин граф, который был введен в употребление Кенигом, подразумевает наличие наглядной графической интерпретации рассматриваемого объекта. Эйлер отождествил с точкой (вершиной графа) каждую часть суши, а каждый мост – с линией (ребром графа), 6 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть C соединяющей соответствующие точки. Получился граф, изображённый на рис. 1.2.

Анализируя этот граф, Эйлер доказал, что сформулированная A L выше задача о мостах не имеет решения.

Важным стимулом к развитию теории графов явилась возникшая в B середине XIX в. задача о четырех Рис. 1.красках. Любую карту на плоскости раскрасить в четыре цвета так, чтобы смежные страны имели различные цвета. Решить эту задачу удалось только в конце ХХ в. с помощью компьютера [11].

1.2. Граф и его дополнение Графом G(V, E) называется совокупность двух множеств – непустого множества объектов некоторой природы V (вершин графа) и множества E неупорядоченных пар элементов множества V, называемых ребрами графа (V, E V V). Таким образом, граф определяется множеством вершин V, множеством рёбер E (подмножеством двухэлементных подмножеств множества V) и отношением инцидентности, которое каждому ребру сопоставляет одну или две вершины. При изображении графов на рисунках отрезки (ребра) могут быть криволинейными и прямолинейными, а длины отрезков и расположение точек произвольно. Будем рассматривать только такие графы, у которых множества V(G) и E(G) конечны (n = n(G) =V, m = m(G) =E) [11 – 16].



Ребро графа называется звеном, если у него два конца, и петлей, если конец один (петля это ребро, у которого два конца совпадают).

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

Глава 1. Основные понятия теории графов Один и тот же граф n = 4, m = Граф-вершина Граф-петля Граф-звено n = 5, m = 8 n = 5, m = 2 n = 3, m = Граф куба Граф с петлями Рис. 1.Вершины графа будем обозначать буквами русского и латинского алфавитов или цифрами, а ребра графа – парами вершин (А, B), (В, С) или буквами латинского алфавита.

Мультиграфом называется пара множеств, состоящая из множества вершин и множества ребер, причем две вершины могут быть соединены более чем одним ребром. Например, граф на рис. 1.4 является мультиграфом.

8 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть Говорят, что вершины графа x, y – смежные, если они соединены ребром. Поэтому вершины C и D на рис. 1.4 являются смежными, а D и A – нет.

B A D C Рис. 1.Граф называется полным, если любые две различные его вершины соединены одним и только одним ребром. Такой граф имеет максимальное число ребер. Каждой вершине в полном графе с n вершинами, который в дальнейшем будем обозначать Kn, принадлежит (n – 1) ребро. Но в произведении n(n – 1) каждое ребро учитывается дважды, поэтому в полном графе n(n – 1)/2 ребер. На рис. 1.5 приведены примеры полных графов: K3, K4, K5.

Рис. 1.Граф, не являющийся полным, можно преобразовать в полный, добавив к нему недостающие ребра. Дополнением графа G называется граф D с теми же вершинами, что и граф G, и теми и только теми ребрами, которые необходимо добавить к графу G, чтобы Глава 1. Основные понятия теории графов получился полный граф. На рис. 1.6 представлен неполный граф и его дополнение.

Неполный граф G Полный граф Дополнение графа G Рис. 1.В табл. 1.1 приведено число различных графов с n вершинами и m n(n – 1)/2 ребрами, которые можно получить из полного графа [3].

Таблица 1. n 23 4 m 0 1 21 31 42 51 61 10 2 4 11 В общем случае, в графе число ребер, которым принадлежит та или иная вершина, различно.

Степенью (валентностью) А вершины А называется число рёбер графа, которым принадлежит эта вершина (число ребер, инцидент10 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть ных вершине А, причем петля считается дважды). На рис. 1.7 представлены графы с различными степенями вершин.

A C B C A B A D D C B D F E А = 1 F = 2 D = 3, А = Рис. 1.Вершина А является четной, если А – четно, и нечетной, если А – нечетно. Вершины, у которых А = 1, называются висячими.

У полного графа с n вершинами степень любой вершины А = n – 1, для изолированной вершины А = 0.

Утверждение 1.1. Во всяком графе G сумма степеней всех его вершин число четное, равное удвоенному числу ребер графа.

Доказательство. При определении степеней вершин графа каждое ребро учитывается два раза, поэтому n = 2 p, i i=где n – число вершин, p – число ребер.

Утверждение 1.2. Во всяком графе с n вершинами (n 2) всегда найдется по крайней мере две вершины с одинаковыми степенями.

Доказательство. Каждая вершина графа с n вершинами может иметь степень 0,1,2,…, n – 1. Пусть все вершины имеют разную степень. Но этого не может быть, так как если есть вершина степени 0, то не может быть вершины степени n – 1 (так как она может быть соединена всего лишь с n – 2 оставшимися вершинами). Таким образом, найдутся хотя бы две вершины с одинаковыми степенями.

Часть вершин графа G и все инцидентные к ним рёбра образуют подграф графа G. Если такой подграф полный, то он называется кликой графа G. Очевидно, что множество подграфов определяется количеством вершин исходного графа. Все вершины и часть инциГлава 1. Основные понятия теории графов дентных им рёбер называется суграфом (остовным подграфом) графа G. Например, на рис. 1.8 приведены подграф и суграф графа G1.

x1 x5 x1 x1 xG1:

x2 x3 x4 x2 x3 x4 x2 x3 xПодграф G1: Суграф G1:

Рис. 1.Если А и В два множества, то для них можно ввести следующие операции: объединение, разность и пересечение множеств. На рис. 1.9 для этих операций приведены диаграммы Эйлера.

Рис. 1.Соответствующие операции (объединение, разность и пересечение) вводятся и для графов. При этом предполагается, что при удалении вершины графа удаляются и все инцидентные ей ребра. На рис.1.10 для графов G1 и G2 приведены графы G1 G2, G1\G2, G1G2.

x1 x5 xG1: G2:

x2 x3 x4 xx1 x5 x5 xx2 x3 x4 x3 x4 xG1 G2 G1\G2 G1GРис. 1.12 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть Используя символы таблицы Менделеева, в химии графы применяются для изображения молекул. Например, на рис. 1.11 представлены мультиграфы молекул ацетилена (C2H2) и этилена (C2H4).

HH CC CC HH HH Рис. 1.1.3. Маршрут в графе, цикл, связанность Рассмотрим граф на рис. 1.12, в котором из вершины x1 в x5 можно попасть различными способами.

Маршрутом в графе называется чередующаяся последовательность вершин ai и ребер ei a = a0, e0, a1, e1, …, en–1, an = b, где ei = (a1, ai+1), a – начало маршрута, b – конец маршрута. Маршрут можно задавать, например, перечислением его вершин (a0, a1,…, an).





В маршруте ребра и вершины могут повторяться. Если в нем все ребра различны, то он называется цепью. В цепи вершины могут повторяться. Если все вершины в цепи различны, то она является простой цепью. Например, на рис. 1.12 последовательность вершин x1, x2, x3, x4, x6, x4, x5 является маршрутом из x1 к x5, а вершины x1, x6 xx2, x3, x4, x5 определяют простую цепь (простой путь) из x1 в x5.

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

Глава 1. Основные понятия теории графов Циклом называется замкнутая цепь, в которой совпадают ее начальная и конечная вершины. Простым циклом в графе называется простая замкнутая цепь. На рис. 1.12 x2, x3, x4, x6, x5, x4, x2 – цикл, x2, x3, x4, x2 – простой цикл. Очевидно, что в простом цикле с n вершинами (n 3), который будем обозначать Сn, содержится n рёбер. На рис.1.13 представлены простые циклы: С3, С5, С6. Длина цикла измеряется числом рёбер в этом цикле.

C C B B B D A D A C A E F E Рис. 1.В простой цепи число вершин на единицу больше, чем число ребер, а в простом цикле их количество совпадает.

Для графа G на рис. 1.14 все циклы длины 4: (AB, BC, CD, DA), (AE, ED, DC, CA), (AD, DE, EB, BA), (AC, CB, BE, EA), являются простыми.

B A C E D Рис. 1.Утверждение 1.3. В графе G любой цикл содержит простой цикл.

14 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть Доказательство. При числе ребер m = 1 цикл (петля с одним ребром) является простым. Пусть утверждение верно для циклов длины не больше m – 1. Рассмотрим произвольный цикл С длины m.

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

Утверждение 1.4. Если у графа G все простые циклы четной длины, то граф не имеет ни одного цикла нечётной длины.

Доказательство. 1. Если граф является простым циклом, то доказательство очевидно.

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

F A C E B D Рис. 1.В такой вершине цикл можно разделить на два: четной и нечетной длины. Будем продолжать расчленять непростые нечетные циклы на четные и нечетные, пока не дойдем до простых циклов. Один из таких циклов должен иметь нечетную длину. А это противоречит условию, что все циклы четные.

Две вершины А и В графа G называются связанными, если в графе есть цепь (путь) с концами А и В. Две вершины А и В не связаны в G, если в графе нет ни одного пути, связывающего их. Граф называется связным, если любые две его вершины связаны. Граф называется Глава 1. Основные понятия теории графов несвязным, если хотя бы две его вершины не связаны. Например, на рис. 1.16 представлен связный (1.16, а) и несвязный (1.16, б) граф.

D B C E A FK Связный граф Несвязный граф аб Рис. 1.Назовем расстоянием d(u, v) длину кратчайшей простой цепи между вершинами u и v в графе G, тогда d(u, u) = 0, uV. Если вершина v недостижима из u, то полагаем d(u, v) =. В связном графе G расстояние обладает следующими свойствами (удовлетворяет аксиомам метрики):

1) d(u, v) 0 и d(u, v) = 0 тогда и только тогда, когда u = v;

2) d(u, v) = d(v, u), u, vV(G);

3) d(u, v) d(u, w) + d(w, v), u, v, wV(G).

Эксцентриситет вершины u графа G есть величина e(u) = max d(u,v),v V (G).

Наибольшее расстояние между вершинами называется диаметром графа (diam(G)), а минимальный из эксцентриситетов вершин связного графа называется радиусом графа (rad(G)). Вершина u, для которой достигается минимум e(u), называется центральной.

Множество всех центральных вершин образует центр графа.

Например, у простого цикла С6 диаметр и радиус совпадают, а каждая вершина является центральной. Для полных графов Kn:

diam(G) = rad(G) = 1.

16 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1.4. Компоненты связности графа Точкой сочленения связного графа называется вершина, после удаления которой граф становится несвязным (ребро с таким же свойством называется мостом). Неразделимым графом называется связный, непустой, не имеющий точек сочленения граф. Блок графа – это максимально неразделимый подграф. На рис. 1.17 граф имеет две точки сочленения, мост и четыре блока.

D X C D С – точки сочленения, Х – мост, Блоки Рис. 1.Вершинной связностью графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному (одновершинному) графу. Следовательно, связность несвязного графа = 0, связность связного графа с точкой сочленения = 1. Если в полном графе Kn удалить n – 1 вершину, то получим тривиальный граф, поэтому для такого графа = n – 1. Для простого цикла всегда (Cn) = 2. На рис. 1.18 для полного графа K4 и простого цикла C8 вершинная связность (K4) = 3, (C8) = 2.

K4 СРис. 1.Глава 1. Основные понятия теории графов Рассмотрим граф на рис. 1.19 с точкой сочленения C. Удалив эту вершину, получим несвязный граф.

С (G)=Рис. 1.Однако чтобы этот граф стал несвязным путем удаления ребер, надо в нем удалить не менее трех ребер. Числом реберной связности (G) называется наименьшее число ребер, удаление которых приводит к несвязному графу. Для любого графа G верны неравенства (G) (G) (G), где (G) – минимальная степень вершин графа G.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 7 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.