nbbzibd0Bw

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ

Н.Р. Ланина

ТЕОРИЯ ГРАФОВ

Учебно-методическое пособие для студентов заочной формы обучения

по направлению подготовки 080500.62 «Бизнес-информатика»

МУРМАНСК

2014

УДК 519.17 (075.8) ББК 22.174я73

Л22

Печатается по решению Совета по научно-исследовательской работе и редакци- онно-издательской деятельности Мурманского государственного гуманитарного университета

Рекомендовано к печати учебно-методическим советом МГГУ к использованию в учебном процессе (протокол № 4 от 28.02.2014 г.)

Автор: Н.Р. Ланина, канд. тех. наук, доцент кафедры математики и математических методов в экономике МГГУ

Рецензенты: Б.М. Верещагин, канд. физ.-мат. наук, доцент кафедры математики и математических методов в экономике МГГУ; Р.А. Богомолов, канд. физ.-мат. наук, доцент кафедры ВМ и ПО ЭВМ МГТУ

Ланина Н.Р.

Теория графов : учебно-методическое пособие для студентов заочной формы обучения по направлению подготовки 080500.62 «Бизнес-информатика» / Н.Р. Ланина.

–Мурманск: МГГУ, 2014. – 104 с.

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

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

Печатается в авторской редакции

© Ланина Н.Р., 2014

2

ВВ Е Д Е Н И Е

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

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

Термин «граф» («graph») впервые ввел венгерский математик Денеш Кёниг (Dénes Kőnig) в своей книге «Теория конечных и бесконечных гра-

фов», напечатанной в Лейпциге в 1936 году.

Примерами графов могут служить схемы метрополитена, железных

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

Начало теории графов положил Леонард Эйлер (Leonhard Euler) в его знаменитом рассуждении о кёнигсбергских мостах (1736 год). Это исследование было единственным в течение почти ста лет. Интерес к проблеме теории графов вновь возник около середины 19-го века в связи с исследованиями электрических сетей, моделей кристаллов и структур молекул.

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

Данное пособие, в первую очередь, предназначено для студентов заочного отделения по направлению 080500.62 «Бизнес-информатика». В учебном плане этой специальности дисциплина «Дискретная математика» входит в базовую часть блока «Математический и естественнонаучный цикл».

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

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

3

примеров и поясняющих рисунков призвано облегчить понимание теоретического материала.

Все материалы данного пособия апробированы автором в течение пятнадцати лет преподавания курсов «Дискретная математика» и «Комбинаторные алгоритмы» студентам математических и программистских специальностей.

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

Начало и окончание доказательства каждой леммы и теоремы отмечены символом «ÿ».

Автор выражает признательность рецензентам ‒ доценту кафедры математики и математических методов в экономике Мурманского государственного гуманитарного университета Б.М. Верещагину и доценту кафедры ВМ и ПО ЭВМ Мурманского государственного технического университета Р.А. Богомолову, чья детальная и благожелательная критика во многом способствовала улучшению первоначального текста рукописи.

4

§1. Элементы теории множеств

п.1.1. Множество. Способы задания множеств

Одним из основных исходных понятий математики является понятие множества и его элементов. Множество состоит из элементов. Множества обозначаются большими латинскими буквами: A; B; C..., а их элемен-

ты ‒ малыми буквами: a1, a2,..., an,...; b1, b2,..., bm,...; c1, c2,..., ck,...

Если a является элементом множества A или, что то же самое, a принадлежит множеству A, то применяют запись aÎA; в противном случае пишут aÏA.

Два множества A и B равны (A=B), если они состоят из одних и тех же элементов. Если множества A и B не равны, то применяется запись

A ¹ B.

Множество, содержащее конечное число элементов, называется конечным, в противном случае множество называется бесконечным. Конечное множество, содержащее n элементов, называется n-множеством.

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

Для задания перечислением множества A, состоящего из элементов a1, a2,..., an, обычно применяется запись A={a1, a2,..., an}, причём порядок элементов в фигурных скобках не имеет значения; обычно он определяется соображениями наглядности.

Пример. В записи множества первых n натуральных чисел Nn = {1, 2,..., n} удобно располагать числа в возрастающем порядке, хотя при этом надо иметь в виду, что

N3 ={1, 2, 3} = {2, 1, 3} = {3, 2, 1}.

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

A ={a / a обладает свойством P(a)}.

Пример. Множество чётных чисел M может быть задано так: M = {i / i ‒ целое число, которое делится на 2 без остатка}.

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

5

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

Возможно также рекурсивное задание множества, при котором осуществляется последовательное описание элементов через предыдущие. Например, множество натуральных чисел рекурсивно можно задать так:

N = {i / если целое iÎN, то i+1ÎN, i ³ 1}.

Мощностью конечного множества A = {a1, a2,..., an} называется количество его элементов n (обозначение: |A| = n).

Очевидно, что если А = В, то |A| = |B|. Кроме того, |Æ| = 0.

Примеры.

1)A ={‒2, ‒1, 0, 1, 2}, |A| = 5;

2)B ={b / b делится на 3 без остатка и b £ 21, bÎN}, |B| = 7.

Если каждый элемент а множества В, аÎВ, является элементом множества А, аÎА, то В называется подмножеством множества А (рисунок 1.1, а). Этот факт записывается с помощью знака включения Í следующим образом: В Í А. В этом случае говорят, что множество В принадлежит множеству А. Принято считать, что пустое множество является подмножеством любого множества.

Свойства включения

1)А Í А;

2)если А Í В и В Í С, то А Í С (рисунок 1.1, б);

3)из двух включений В Í А и А Í В следует, что А = В.

Рисунок 1.1.

Пример. Составить все подмножества для A = {3, 6, 9}.

Решение. Их восемь: Æ, {3}, {6}, {9}, {3, 6}, {3, 9}, {6, 9}, {3, 6, 9}.

6

п. 1.2. Операции над множествами

Объединением двух множеств А и В называется множество, которое содержит как элементы множества A, так и элементы множества B (рисунок 1.2, а):

AÈB = {a / aÎA или aÎB}.

Пересечением двух множеств А и В называется множество, которое содержит общие элементы, т.е. те, которые присутствуют и в A, и в В (рисунок 1.2, б):

AÇB = {a / aÎA и aÎB}.

Если множества А и В не имеют общих элементов, то их пересечением является пустое множество:

AÇB = Æ.

Пример 1.2. Если A = {12, 15, 18}, B = {12, 14, 16, 18, 20}, то AÈB = {12, 14, 15, 16, 18, 20}, AÇB = {12, 18}.

Рисунок 1.2 – а) Объединение множеств А и В; б) пересечение множеств А и В.

Семейство множеств {A1, A2, ..., Am} называется покрытием множества А, если имеет место равенство

A = A1 È A2 È ... È Am.

Множества A1, A2, ..., Am называются блоками покрытия.

Пример. Множества {1, 2, 3, 5, 7}, {3, 6, 9}, {2, 4, 6, 8} образуют покрытие множества {1, 2, 3, 4, 5, 6, 7, 8, 9}.

7

Важным частным случаем покрытия является разбиение. Семейство множеств {A1, A2,..., Am} называется разбиением множества А, если это покрытие, блоки которого не пустые и попарно не пересекаются, т.е.

A = A1 È A2 È ... È Am, Ai ¹ Æ, AiÇAj = Æ, если i ¹ j, 1 £ i, j £ m.

Множества A1, A2, ..., Am называются блоками разбиения.

Порядок записи блоков может быть произвольным. Например, два разбиения {1, 2, 9}È{5, 7} и {5, 7}È{1, 2, 9} множества {1, 2, 5, 7, 9} считаются совпадающими.

Пример 1.3. Составить все возможные разбиения множества А = {1, 2, 3}.

Решение. {1}È{2, 3}; {2}È{1, 3}; {3}È{1, 2}; {1}È{2}È{3}.

Разность множеств А и В представляет собой множество, которое содержит элементы А и при этом не содержит элементы В (рисунок 1.3, а):

A\B = {a / aÎA и aÏB}.

Пример. По условию примера 1.2 A\B = {15}, В\А = {14, 16, 20}.

Пользуясь понятием универсального множества, можно определить дополнение A к множеству А, как разность вида (рисунок 1.3, б):

A = U \ A.

Рисунок 1.3 – а) Разность множеств А и В; б) дополнение к множеству А.

Пример. Пусть в качестве универсального множества выступает множество целых чисел Z и пусть А ‒ это множество всех чётных чисел. Тогда A ‒ это множество всех нечётных чисел.

8

п. 1.3. Кортеж. Прямое произведение

Кортеж ‒ это упорядоченный набор элементов. Кортеж характери-

зуется элементами и порядком их расположения. Элементы кортежа называются компонентами. Компоненты нумеруют слева направо. Число компонент определяет длину кортежа. Кортеж обозначается (a1, a2, ..., an). Кортеж длиной в две компоненты называют упорядоченной парой (или

просто парой), кортеж длиной в три компоненты ‒ тройкой и т.д.

Два кортежа равны, если они имеют одинаковую длину и их соответствующие координаты равны, т.е. (a1, a2, ..., an) и (b1, b2, ..., bm) равны, если m = n и a1 = b1, a2= b2, ..., an = bn .

Прямым (декартовым) произведением множеств А и В (обозначение:

А×В) называется множество всех пар (a, b), таких, что а А, b B. В частности, если А = В, то обе координаты принадлежат А. Такое произведение обозначается A2.

Примеры.

1.Пусть A = {x, y}. Тогда A2 = А×A = {(x, x), (x, y), (y, x), (y, y)}.

2.Пусть A = {a, b}, B = {p, s, t}.

Тогда А×В = {(a, p), (a, s), (a, t), (b, p), (b, s), (b, t)}.

3. Пусть A = {a, b, c, d, e, f, g, h}, B = {1, 2, 3, 4, 5, 6, 7, 8}.

Тогда А×В = {(a, 1), (a, 2), (a, 3),... , (h, 7), (h, 8)} ‒ множество, содержащее обозначение всех 64 клеток шахматной доски.

Теорема 1.1. Пусть множество A содержит n элементов, т.е. |A|=n, а множество B содержит m элементов, т.е. |B|=m.

Тогда |А×В| = n ∙ m.

ÿ

Пронумеруем элементы множеств А и В:

A= {a1, a2, ..., an}, B = {b1, b2, ..., bm}

исоставим декартово произведение этих множеств, для наглядности рас-

положив элементы в n строках и m столбцах:

А×В = { (a1, b1), (a1, b2), ... (a1, bm), (a2, b1), (a2, b2), ... (a2, bm),

...

(an, b1), (an, b2), ... (an, bm) }

Очевидно, общее количество элементов |А×В| = n ∙ m.

ÿ

9

Аналогично, прямым произведением множеств A1, A2, ..., An (обозначение: A1×A2×...×An) называется множество всех кортежей (a1, a2, ..., an), та-

ких, что a1 A1, a2 A2,..., an An.

При A1 = A2 = ... = An вместо A1×A2×...×An записывают An.

Пример. Пусть B={0,1}. Тогда

B3 = B×B×B = {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}.

п. 1.4. Бинарные отношения. Отношение эквивалентности

Пусть M ‒ некоторое множество; M 2 = M×M ‒ прямое произведение

множества M на себя.

Подмножество R множества M 2 называется бинарным отношением на множестве М, т.е. R M 2.

Говорят, что элементы a и b множества M находятся в отношении R,

если (a, b) R.

Примеры 1.4.

1. Пусть M = {3, 8, 24}. Тогда M 2 = М×М = {(3, 3), (3, 8), (3, 24), (8, 3), (8, 8), (8, 24), (24, 3), (24, 8), (24, 24)}.

а) Отношение «<» на множестве М:

R1 = {(a, b) / a < b; a, b М} = {(3, 8), (3, 24), (8, 24)}. б) Отношение «быть делителем» на множестве М:

R2 = {(a, b) / a ‒ делитель b; a, b М} =

={(3, 3), (3, 24), (8, 8), (8, 24), (24, 24)}.

2.Пусть M ‒ множество точек действительной плоскости, т.е. M = R×R, где R ‒ множество действительных чисел.

а) Отношение R3 «находиться на одинаковом расстоянии от начала координат» выполняется, например, для пары точек (3, 4) и (0, 5), но не вы-

полняется для пары точек (3, 4) и (1, ‒6).

б). Отношение R4 «быть симметричными относительно оси (ОХ)» выполняется для всех пар точек (x1, y1) и (x2, y2), удовлетворяющих условию:

x1 = x2; y1 = ‒y2.

3. Пусть M ‒ множество жителей города Мурманска, зарегистрированных на 1 января 2014 года. Зададим следующие отношения на этом множестве:

10