Конспект_лекций_по_курсу_Дискретная_математика

x y(xRy x y) , т.е. из принадлежности любой пары (x, y) отношению R следу-

ет, что первый элемент этой пары не совпадает со вторым. Иначе говоря, ни одна пара вида (х, х) не входит в отношение.

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

Пример 1.4.16. 1. Пусть Х – множество людей; R = {(x, y)| x – брат y}. Так как ни один человек не может быть братом самому себе, то это отношение антиреф-

лексивно.

2. Пусть Х – множество участников шахматного турнира; R = {(x, y)| x – побе-

дитель y}. Так как ни один участник турнира не играет сам с собой и, следователь-

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

3. Пусть Х – множество прямых на плоскости; R = {(x, y)| прямая x перпенди-

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

Очевидно, что отношение не может одновременно обладать свойствами реф-

лексивности и антирефлексивности – эти свойства несовместимы друг с другом.

3) Симметричность

Отношение R на множестве Х называется симметричным, если

x y(xRy yRx) , т.е. из принадлежности любой (x, y) отношению R следует, что и противоположная пара (y, x) R.

Матрица симметричного отношения симметрична относительно главной диа-

гонали. В графическом представлении каждой стрелке, идущей от одного объекта к другому, соответствует стрелка, идущая в противоположном направлении.

Пример 1.4.17. 1. Пусть Х – множество людей; R = {(x, y)| x – знаком с y}. Так как из знакомства человека х с человеком y следует, что и человек y знаком с чело-

веком х, то это отношение симметрично.

2. Пусть Х – множество треугольников; R = {(x, y)| х подобен y}. Так как из подобия треугольника х треугольнику y следует и подобие треугольника y тре-

угольнику х, то это отношение симметрично.

-31-

3. Пусть Х – множество прямых на плоскости; R = {(x, y)| прямая x перпенди-

кулярна прямой y}. Так как из того, что прямая х перпендикулярна прямой y сле-

дует, что и прямая y перпендикулярна прямой х, то отношение перпендикулярно-

сти прямых симметрично.

4) Асимметричность

Отношение R на множестве Х называется асимметричным, если

x y((x, y) R ( y, x) R) , т.е. ни одной паре (x, y), принадлежащей отношению,

не соответствует противоположная пара (y, x).

Пример 1.4.18. 1. Пусть Х – множество участников шахматного турнира;

R = {(x, y)| x – победитель y}. Так как из того, что игрок х победил в турнире игро-

ка y, следует, что игрок y не победил игрока х, то это отношение асимметрично.

2.Пусть Х – множество людей; R = {(x, y)| x – отец y}. Если х – отец y, то y не может быть отцом х, следовательно, это отношение асимметрично.

3.Пусть Х – множество людей; R = {(x, y)| x младше y}. Если x младше y, то y

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

5) Антисимметричность

Отношение R на множестве Х называется антисимметричным, если

x y((xRy yRx) y x) , т.е. одновременная принадлежность отношению обеих пар (x, y) и (y, x) возможна только тогда, когда оба элемента этих пар одинаковы.

Очевидно, что отношение не может быть одновременно симметричным,

асимметричным и антисимметричным – эти свойства несовместимы друг с другом.

Пример 1.4.19. 1. Пусть Х – множество целых чисел; R = {(x, y)| х – делитель y}. Если х является делителем y и одновременно y является делителем х, то отсюда следует, что х и y одно и то же число, т.е. отношение делимости антисимметрично.

2.Пусть Х – множество вещественных чисел; R = {(x, y)| х y}. Если х y и y

x, то это значит, что x = y и, следовательно, отношение нестрогого неравенства антисимметрично.

-32-

6) Транзитивность

Отношение R на множестве Х называется транзитивным, если

x y z((xRy yRz) xRz) , т.е. из того, что пара (x, y) R и пара (y, z) R следует,

что также и пара (x, z) R.

Пример 1.4.20. 1. Пусть Х – множество целых чисел; R = {(x, y)| х – делитель y}. Очевидно, что если число х является делителем числа y, а число y является де-

лителем числа z, то х является делителем числа z, таким образом, условие транзи-

тивности выполняется.

2. Пусть Х – множество треугольников; R = {(x, y)| х подобен y}. Очевидно,

что если треугольник х подобен треугольнику y, а треугольник y подобен тре-

угольнику z, то треугольник х подобен треугольнику z, следовательно, отношение подобия обладает свойством транзитивности (это, очевидно, справедливо не толь-

ко для треугольников, но и для любых геометрических фигур).

1.4.2.5. Виды отношений

1) Отношение эквивалентности

Отношение E называется отношением эквивалентности, если оно одновре-

менно рефлексивно, симметрично и транзитивно.

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

отношение параллельности на множестве прямых и т.п.

Если на множестве X задано отношение эквивалентности и пара (x, y) принад-

лежит этому отношению, то мы будем обозначать это символом тильда : x y

(читается "x эквивалентно y").

Множество элементов y, эквивалентных данному элементу x, называется

классом эквивалентности элемента x: E(x) = {y| x y}. Множество всех классов эквивалентности, определенных на множестве X с помощью отношения эквива-

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

пользуется знак \).

-33-

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

множеством – множество учебных групп университета.

2. Для отношения параллельности на множестве прямых классом эквивалент-

ности является множество прямых, параллельных данной прямой, а фактор-

множеством – множество классов эквивалентности всех не параллельных друг другу прямых.

Каждое непустое множество X может быть разбито на непересекающиеся подмножества Xi, каждое из которых не является пустым. Множество таких под-

множеств называется разбиением множества X. Если таких подмножеств n, то

n

объединение всех этих подмножеств совпадает с X: X i X , а X i X j , если

i 1

i ≠ j.

Можно доказать, что фактор-множество X/E является разбиением множества

X, и наоборот, если каким-то образом выполнено разбиение множества X, то все-

гда можно задать соответствующее ему отношение эквивалентности E по следую-

щему правилу: xEy x, y Xi для некоторого i.

2) Отношение частичного порядка

Отношение R называется отношением частичного порядка, если оно одно-

временно рефлексивно, транзитивно и антисимметрично.

Пример 1.4.23. Отношение делимости на множестве натуральных чисел, от-

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

3) Отношение строгого частичного порядка

Отношение R называется отношением строгого частичного порядка, если оно транзитивно и асимметрично.

Пример 1.4.23. Отношение строгого неравенства на множестве веществен-

ных чисел, отношение "быть предком" на множестве людей.

-34-

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

2.1.Основные понятия и определения

2.1.1.Определение графа

Графом называется пара Х, Г , где Х – некоторое непустое множество, а

Г Х Х, т.е. в смысле этого определения граф представляет собой в сущности от-

ношение на множестве Х.

Втеории графов Г часто называют отображением множества Х в себя.

2.1.2.Способы задания графов

Поскольку графы являются отношениями, то и задаются они так же, как от-

ношения.

1)аналитический способ задания: задаются Х и Г (т.е. множество входящих

вГ пар) или Х и множество образов всех элементов множества Х, иногда называе-

мое фактор-множеством множества Х по отображению Г (обозначается Х/Г).

Пример 2.1. 1. Х = {х1, ..., х5}; Г = {(х1, х2), (х1, х5), (x2, х1), (x2, x3), (x2, x4), (x4, х1), (x4, х2), (x4, x5), (x5, x3), (x5, x5)} – задание графа перечислением пар, входя-

щих в Г.

2. Х = {х1, ..., х5}; X/Г = {Гх1 = {х2, х5}, Гx2 = {x1, x3, x4}; Гx3 = ;

Гx4 = {x1, x2, x5}; Гx5 = {x3, x5}} – задание того же графа с помощью фактормножества.

2) графический способ задания: множество X изображается в виде точек на плоскости, называемых вершинами графа; отображение Г задается линиями со стрелками, направленными от вершин к их образам. Эти линии называются

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

Дуга, конец которой совпадает с ее началом, называется петлей.

Пример 2.2. Графическое представление графа из примера 2.1 (рис. 2.1).

-35-

	x3
x2	x4
x1	x5

Рис. 2.1

3) матричный способ задания: каждой вершине графа ставится в соответст-

вие строка и столбец матрицы. Если из вершины xi в вершину xj идет дуга, т.е.

вершина xj входит в состав образа вершины xi (xj Гxi), то на пересечении строки xi и столбца xi ставится 1, в противном случае – 0. Такая матрица называется мат-

рицей смежности графа.

Пример 2.3. Граф из примера 2.1 имеет следующую матрицу смежности:

x1	x2	x3	x4	x5
x 0	1	0	0	1
1
x2 1	0	1	1	0
R (rij ) x3 0	0	0	0	0
x4 1	1	0	0	1
x5 0	0	1	0	1

Если для какой-либо пары вершин (xi, xj) rij = rji, то в графическом представле-

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

Граф, состоящий только из звеньев, называется неориентированным графом,

или сокращенно неографом.

Граф, в котором звенья отсутствуют, называется ориентированным графом,

или орграфом.

Если в графе есть и дуги, и звенья, то он называется смешанным.

Совокупность дуг и звеньев принято называть ребрами.

Пример 2.4. 1. План города можно представить в виде графа, вершинам кото-

рого соответствуют перекрестки, а ребрам – улицы, причем улицам с односторон-

-36-

ним движением ставятся в соответствие дуги, а улицам с двусторонним движени-

ем – звенья.

2. Результаты шахматного турнира можно представить в виде графа, в кото-

ром вершинам соответствуют игроки, дуга идет от победителя к побежденному, а

звено связывает участников, сыгравших вничью.

Иногда наряду с орграфом или смешанным графом необходимо рассматри-

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

ны звеньями. Такой неограф называется соотнесенным неографом.

Если вершина является началом или концом какого-либо ребра, то говорят,

что эта вершина инцидентна этому ребру (дуге, звену), а ребро инцидентно этой вершине.

Вершина, не инцидентная ни одному ребру графа, называется изолирован-

ной. Граф, состоящий только из изолированных вершин, называется нуль-

графом.

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

В отличие от обычных отношений в графе пары вершин могут быть соедине-

ны несколькими ребрами, имеющими одну и ту же ориентацию. Такие ребра на-

зываются кратными, а граф, в котором имеются кратные ребра, называется муль-

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

называется кратностью. Кратность ребра (xi, xj) обозначается (xi, xj). Эта величи-

на ставится в матрице смежности вместо единиц и нулей.

Пример 2.5. 1. План города, где имеются улицы с многополосным движени-

ем: каждая дуга означает полосу движения; кратность – количество полос для движения в одном направлении;

2. Результаты турнира, проводящегося в несколько кругов: кратность – коли-

чество побед одного участника над другим.

Иногда возникает необходимость указания на графе дополнительной инфор-

мации об объектах, представленных ребрами графа, например, длины участка до-

-37-

роги или ее пропускной способности, или мощности линии электропередачи и т.п.

Эта информация записывается при графическом представлении графа рядом с ду-

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

щая матрица называется матрицей мер. Мера ребра (xi, xj) обозначается (xi, xj).

Соответствующий граф называется графом с нагруженными ребрами.

2.1.3. Пути, контуры, цепи и циклы в графе

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

Путь называется простым, если он не содержит повторяющихся дуг. В про-

тивном случае путь называется составным.

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

щихся вершин.

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

ная вершина совпадают. Как и другие пути, контуры могут быть простыми, со-

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

Внеографах аналогом пути является цепь (составная, простая, элементарная),

ааналогом контура – цикл (составной, простой, элементарный).

Количество ребер, из которых состоит путь (цепь, контур, цикл), называется его длиной. При определении длины составного пути (цепи, контура, цикла) по-

вторяющиеся ребра учитываются столько раз, сколько они встречаются в этом пу-

ти.

Пример 2.6. В графе, представленном на рис. 2.2, путь (x1, x2, x4, x1, x2, x3) яв-

ляется составным, так как в нем дуга (x1, x2) содержится дважды; путь (x2, x4, x1, x2, x3) - простой, но не элементарный, так как в нем вершина x2 встречается дважды;

путь (x4, х1, x2, x3) - элементарный, так как он не содержит повторяющихся вершин.

-38-

x3

x2 x4

x1	x5

Рис. 2.2

В этом графе контур (x4, x2, x4, х1, x2, x4) - составной, (х1, x5, x3, х1, x2, x4, х1) – простой, но не элементарный, (х1, x2, x4, х1) – элементарный.

2.2. Операции над графами

Над графами выполняются те же операции, что и над отношениями на мно-

жествах. Особенности имеют место только в композиции мультиграфов.

Пусть G1 = X, Г1 и G2 = X, Г2 – два графа, заданных на одном и том же множестве вершин X. Рассмотрим их композицию, которая представляет собой граф на том же множестве вершин. Если это обычные графы, то дуга (xi, xj) при-

надлежит композиции G1 G2 тогда и только тогда, когда существует путь

(xi, xk, xj), состоящий из двух ребер, в котором дуга (xi, xk) принадлежит графу G1, а

дуга (xk, xj) принадлежит графу G2. Если таких путей несколько, то в композицию все равно включается только одно ребро.

Если же G1 и G2 – мультиграфы, то в их композицию включается столько дуг

(xi, xj), сколько существует путей длины 2 вида (xi, xk, xj), в которых дуга (xi, xk)

принадлежит графу G1, а дуга (xk, xj) – графу G2.

Пример 2.7. На рис. 2.3 представлены два графа G1 = (X, Г1) и G2 = (X, Г2), а

на рис. 2.4 и их композиции: а) для случая, когда оба эти графа рассматриваются как обычные графы; б) для случая, когда эти графы рассматриваются как мульти-

графы с однократными ребрами.

-39-

x2

G1

x2 G2

x3	x1	x3
x1

Рис. 2.3

x2	x2
а)	б)

x1x3 x1x3

Рис. 2.4

При матричном способе представления графов матрица композиции обычных графов получается как булево произведение матриц смежности исходных графов

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

Упражнение. Выполните операции из предыдущего примера матричным спо-

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

2.3. Частичные графы и подграфы

Граф H = X, называется частичным графом для графа G = X, Г , если они заданы на одном и том же множестве вершин и множество ребер графа H яв-

ляется подмножеством множества ребер графа G, т.е. Г.

Граф GA = A, ГA называется подграфом графа G = X, Г , если A X, а мно-

жество его ребер состоит из всех тех ребер графа G, оба конца которых лежат в множестве А.

Пример 2.8. На рис. 2.5 изображен граф G = X, Г (X = {x1, x2, x3, x4}), один из его возможных частичных графов H = X, и подграф GA = A, ГA , определен-

ный на множестве вершин A = {x1, x2, x4}

-40-