Практикум по дискретной математике (стр. 3 )

2.  Иванов, математика. Алгоритмы и программы: учеб. пособие для вузов / . – М.: Лаборатория базовых знаний, 2002. – 288 с.

3.  Новиков, математика для программистов: учебник для вузов / . – СПб.: Питер, 2005. – 304 с.

3. Практическое занятие № 3

Тема: «Отношения эквивалентности и отношения порядка»

Цель занятия:

усвоение таких понятий, как отношение эквивалентности, классы эквивалентности, отношение порядка.

Пояснение к работе

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какими свойствами обладает отношение строгого порядка?

Что называется классом эквивалентности?

Что называется разбиением множества?

2. Дать определение следующих понятий:

– отношение эквивалентности;

– отношение строгого порядка;

– отношение частичного порядка;

– отношение линейного порядка.

3. Привести пример разбиения множества.

4. Выполнить задания для аудиторных занятий.

5. Выполнить задания для самостоятельной работы.

3.1. Отношения эквивалентности. Отношения порядка

Отношение эквивалентности – бинарное отношение, являющееся рефлексивным, симметричным и транзитивным.

Примеры отношений эквивалентности: 1) отношения равенства, параллельности прямых; 2) отношение между элементами множества всех многоугольников: "иметь одинаковое число сторон"; 3) отношение принадлежности к одной студенческой группе на множестве студентов института – отношение эквивалентности.

Классом эквивалентности, порожденным элементом х, называется подмножество множества Х, состоящее из тех элементов уÎХ, для которых хrу – класс эквивалентности, порожденный элементом х, обозначается через [х]:

[х] = {у׀ уÎХ и хrу}.

Примеры. 1. Отношение равенства на множестве Z порождает следующие классы эквивалентности: для любого элемента х Î Z[х] = {х}, то есть каждый класс эквивалентности состоит из одного элемента – числа х.

2. Множества подобных друг другу треугольников; в разных классах – треугольники разной формы.

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

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

Примеры разбиений множества. 1. Х = {1, 2, 3, 4, 5}, тогда {{1, 2}, {3, 5}, {4}} – разбиение множества Х.

2. Пусть Х – множество студентов института. Тогда разбиением этого множества является, например, совокупность студенческих групп.

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

Рефлексивное, антисимметричное и транзитивное отношение называется отношением частичного (нестрогого) порядка на множестве Х и обозначается символом £.

Примеры отношений частичного порядка. 1. Отношение х £ у на множестве R есть отношение частичного порядка.

2. Во множестве подмножеств некоторого универсального множества U отношение А Í В есть отношение частичного порядка.

3. Схема организации подчинения в учреждении – отношение частичного порядка на множестве должностей.

Отношение частичного порядка на множестве Х, для которого любые два элемента сравнимы, то есть для любых х, уÎХ х £ у или у £ х, называется отношением линейного порядка.

Примеры отношений линейного порядка. 1. Отношение х £ у на множестве R есть отношение линейного порядка.

2. Во множестве подмножеств некоторого универсального множества U отношение А Í В не является отношением линейного порядка.

Задания

Для аудиторных занятий

1. Перечислить всевозможные отношения линейного порядка на множестве {1, 2, 3, 4}.

2. Доказать, что пересечение отношений эквивалентности на множестве Х есть отношение эквивалентности на этом множестве.

3. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x2 + y2 = 25?

4. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x = 2y?

5. Доказать, что если r – частичный порядок, то r-1 – также частичный порядок.

6. Доказать, что каждое из следующих отношений является отношением эквивалентности, и найти классы эквивалентности:

а) пусть А = {1, 2, 3}, на множестве Р(А) задано бинарное отношение хrу Û½х½= ½у½;

б) на множестве N ´ N задано бинарное отношение áa, bñ r ác, dñ Û a + d = b + c;

в) на множестве R: arb Û a2 = b2;

г) на множестве R: arb Û a - bÎZ.

7. На R задано бинарное отношение arb Û a2 + a = b2 + b. Доказать, что r – отношение эквивалентности. Сколько элементов может содержать класс эквивалентности? Существует ли класс эквивалентности, состоящий из одного элемента?

8. Доказать, что отношение áa, bñ r ác, dñ Û a2 + b2 = c2 + d2 является отношением эквивалентности на множестве R × R. Найти классы эквивалентности и изобразить их на координатной плоскости.

9. Показать, что пересечение отношений эквивалентности, определенных на некотором множестве А, является отношением эквивалентности.

Для самостоятельной работы

1.  Доказать, что если r – отношение эквивалентности, то r-1 – также отношение эквивалентности.

2.  Доказать, что если r – отношение эквивалентности, то истинны следующие утверждения ([x]r – класс эквивалентности, порожденный элементом х):

а) х Î[x]r; б) хry Û [x]r = [y]r.

3.  Доказать, что отношение делимости на множестве N является отношением порядка. Является ли это отношение линейным порядком? Является ли отношением порядка отношение делимости на множестве Z?

4.  Доказать, что отношение хry Û x / y Ú х < y на множестве N является линейным порядком.

5.  Для каких множеств А множество {В(А), Í} является линейно упорядоченным?

6.  Пусть А – не пустое конечное множество. На B(А) рассмотрим отношение XrY Û çXç£ çYç. Является ли r отношением порядка?

7.  На множестве всех отображений R в R рассмотреть отношение frq Û ("x Î Rç f(x) = 1, q(x) = 1). Является ли r отношением порядка?

8.  На множестве всех отображений R в R рассмотреть отношение frq Û {x Î Rç f(x) = 0} Í {x Î Rçg(x) = 0}. Является ли r отношением порядка?

9.  Доказать, что отношение áa; bñ r ác; dñ Û a < c Ú(a = c Ù b £ d) является линейным порядком на множестве Z ´ Z.

10.  По аналогии с упражнением 9 определить линейный порядок на множестве А ´ В, если áА, r1 ñ и áВ, r2ñ – линейно упорядоченные множества.

11.  Перечислить всевозможные линейные порядки на множестве {1, 2}; на множестве {1, 2, 3}. Высказать предположение о числе линейных порядков на множестве из n элементов.

12.  Пусть F – множество всех непустых конечных подмножеств множества N. Какие элементы упорядоченного множества áF, Í ñ являются минимальными? Доказать, что áF, Í ñ не содержит максимальных элементов.

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

14.  Доказать:

а) упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента;

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

Литература

1.  Белоусов, математика: учебник / . – М.: МГТУ им. , 2001. – 744 с.

2.  Куликов, задач по алгебре и теории чисел / , , А. А Фомин. – М.: Просвещение, 1993. – 288 с.

3.  Нефедов, дискретной математики: учеб. пособие / , . – М.: Изд-во МАИ, 1992. – 264 с.

4. Практическое занятие № 4

Тема: «Функции и отображения»

Цель занятия:

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

Пояснение к работе

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Как обозначается функция (отображение)?

Что является областью определения функции?

Что является областью значений функции?

Какая функция называется инъективной?

Какая функция называется сюръективной?

Какая функция называется биективной?

В чем заключается понятие однозначности или функциональности?

Чему равна композиция двух функций?

Какое из отношений является функцией:

{<1, 2>, <3, 4>, <4, 4>, <5, 6>}; {<1, 2>, <1, 4>, <4, 4>, <5, 6>}.

2. Дать определение функции.

3. Выполнить задания для аудиторных занятий.

4. Выполнить задания для самостоятельной работы.

4.1. Функции и отображения

Пусть f – отношение на А и В, такое, что "(a, b) Î f и (a, c) Î f Þ b = c. Такое свойство отношений называется однозначностью или функциональностью, а само отношение называется функцией из А в В и обозначается следующим образом: f: A ® B, то есть осуществляется отображение множества А на множество В. Если f: A ® B, то обычно используется префиксная форма записи: b = f(a) := (a, b) Î f. Если b = f(a), то а называют аргументом или прообразом элемента b при функции f, а b – значением функции или образом элемента а при f. Итак, из всех отношений функции выделяются тем, что каждый элемент из области определения имеет единственный образ. Область определения функции: fA:= {a ÎAç$b Î B, b = f(a)}; область значений функции: fВ:= {b Î Bç$a Î A, b = f(a)}.

Функция f называется: инъективной, если b = f(a1) и b = f(a2) Þ а1 = а2; сюръективной, если " b ÎВ $а ÎА b = f(a); биективной, если она инъективна и сюръективна.

Примеры:

1. {<1, 2>, <3, 4>, <4, 4>, <5, 6>} – функция, fА = {1, 3, 4, 5};

fВ = {2, 4, 6}; {<x, y>: x, y Î R, y = x2} – функция, fА = fВ = (–¥, ¥);

{<1, 2>, <1, 4>, <4, 4>, <5, 6>} – отношение, но не функция.

2. Даны три функции, отображающие множество действительных чисел R во множество действительных чисел, fi : R ® R. i = 1, 2, 3:

а) функция f1(х) = ех инъективна, но не сюръективна; б) функция f2(х) = х3 – х сюръективна, но не инъективна; в) функция f3(х) = 2х + 1 биективна.

Композиция двух функций есть функция. При этом, если f: Х ®У, g : Y ® Z, то gOf : Х ® Z.

Задания

Для аудиторных занятий

1. Привести примеры отображений:

а) R ® R;

б) R ® R+;

в) R+ ® R.

2. Найти f(A), где А = {(х, у)Î R ´ R| у = 2 х + 3 }, для следующих отображений:

а) f: (x, y) ® (y, x);

б) f: (x, y) ® (−y, −x);

в) f: (x, y) ® (x, −y).

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

а) f: R ® R, х ® x2 + 3х + 5;

б) f: R ® R, х ® x2 + ex;

в) f: R ® R, х ® x7 + х + 1.

4. Указать все сюръективные отображения множества А = {1, 2, 3} на множество В ={а, b}. Существуют ли инъективные отображения А в В?

5. Пусть А и В – конечные множества, |А| = m, |B| = n.

a) сколько существует бинарных отношений между элементами множеств А и В?

б) сколько существует отображений из А в В?

6. Пусть a: х ® х2; b: х ® х3 – отображения R ® R. Найти a b и b a.

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

а) {(х, у) Î R+ ´ R| у2 = х};

б) {(х, у) Î[ −1, 1] ´ R| х = sin y};

в) {(х, у) Î N ´ N| x < у ≤ х + 1}.

8. Доказать, что каждое из следующих бинарных отношений является отображением R в R:

а) {(х, у) Î R ´ R| у = х2 − 1};

б) {(х, у) Î R ´ R| у = sin х + 1};

в) {(х, у) Î R ´ R| у = 2х}.

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

а)

б)

в)

10. Пусть А и В – конечные множества, ½А½ = ½В½ = n.

а) сколько существует бинарных отношений между элементами множеств А и В?

б) сколько существует отображений А в В?

Для самостоятельной работы

1. Привести примеры отображений:

а) R ® [0, 1];

б) Z ® N;

в) R ® N.

2. Найти f(A), где А = {(х, у)Î R ´ R | у = 2х + 3}, для следующих отображений:

а) f: (x, y)®( −x, y);

б) f: (x, y)®( у − 2, х + 2).

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

а) f: R ® R, х ® 2x5 − 1;

б) f: R ® R, х ® x2 +;

в) f: R ® R, х ® x2 + lnx.

4. Пусть А и В – конечные множества, |А| = m, |B| = n.

а) при каких m и n существует инъективное отображение А в В?

б) при каких m и n существует биекция А на В?

в) пусть существуют биекции А на А’ и В на В’. Доказать, что существует биекция А ´ В на А’ ´ В’.

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

а) {(х, у) Î N ´ N| x/у};

б) {(х, у) Î N ´ N| x = у2};

в) {(х, у) Î Z ´ Z| у = |х|}.

6. Доказать, что каждое из следующих бинарных отношений является отображением R в R:

а) {(х, у) Î R ´ R| у = х2 − x − 1};

б) {(х, у) Î R ´ R| у = log2|х|}.

в) {(х, у) Î R ´ R| у = }.

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

а) {áх, уñ Î N ´ N| x < у £ х + 1};

б) {áх, уñ Î N ´ N| x/у};

в) {áх, уñ Î N ´ N| x = у2}.

8. Указать все сюръективные отображения множества А = {1, 2, 3} на множество B = {a, b}. Существуют ли инъективные отображения А в В?

9. Найти все отображения множества А = {1, 2} в себя, укажите, какие из них инъективные, сюръективные.

10. Пусть f – отображение конечного множества А в себя. Докажите, что f инъективно тогда и только тогда, тогда f сюръективно.

Литература

1.  Куликов, задач по алгебре и теории чисел / , , А. А Фомин. – М.: Просвещение, 1993. – 288 с.

2.  Новиков, математика для программистов: учебник для вузов / . – СПб.: Питер, 2001. – 304 с.

5. Практическое занятие № 5

Тема: «Элементы графа. Способы задания графа. Подграфы.

Изоморфизм»

Цель занятия:

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

Пояснение к работе

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какие вершины графа называются смежными?

В чем заключается понятие инцидентности?

Как задается матрица инциденций для орграфа?

Какой граф называется псевдографом?

Какой граф называется двудольным?

2. Дать определение следующих понятий:

– граф;

– изоморфизм;

– полный граф;

– подграф;

– ориентированный граф.

3. Выполнить задания для аудиторных занятий.

4. Выполнить задания для самостоятельной работы.

5.1. Элементы графа

Граф G – это совокупность двух множеств: непустого множества вершин V = {v1, v2, ..., vn} и множества ребер (дуг) Е = {е1, е2, ..., еn}. Таким образом, G = (V, Е), V ¹ Æ, Е Ì V × V.

Если (v1, v2) – упорядоченная пара (т. е. дуга), то v1 называется началом, a v2 – концом дуги е. Если {v1, v2} – неупорядоченная пара, то ребро е называется неориентированным. Всякому графу G можно поставить в соответствие соотнесенный неориентированный граф G с теми же множествами V и Е и инцидентностями, но все пары неупорядоченные. Такой граф называется ассоциированным. Вершина, не инцидентная ни одному ребру, называется изолированной. Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми или висячими. Ребро с совпадающими концами называется петлей. Две вершины, инцидентные одному и тому же ребру, называются смежными. Два ребра, инцидентные одной и той же вершине, называются смежными. Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными или параллельными.

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

e6

Примеры:

Рис. 3

На рис. 3 изображены: ориентированный псевдограф, имеющий 7 вершин и 6 дуг, и неориентированный мультиграф, имеющий 4 вершины и 5 ребер. Проиллюстрируем некоторые введенные понятия.

Для орграфа (рис. 3а): v1, v2, v3, v4, v5, v6 , v7 – вершины (узлы); v5 – изолированная вершина; v1, v4 – концевые (висячие) вершины; v2 и v3, v2 и v1 – пары соседних вершин; е1, е2, е3, е4, е5, е6 – ориентированные ребра (дуги); е2 и е3 – параллельные (кратные) дуги; е2 и е1 – смежные дуги; е6 –петля для орграфа.

Для графа (рис. 3б): v1, v2, v3, v4 – вершины; v4 – концевая (висячая) вершина; v2 и v3, v2 и v1 – пары соседних вершин; е1, е2, е3, е4, е5 – ребра (дуги); е4 и е5 – параллельные (кратные) ребра; е2 и е3 – смежные ребра; петель нет.

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

1.  Перечисление (список) ребер графа с указанием их концов и добавлением списка изолированных вершин.

2.  Матрица смежности A = (aij) определяется одинаково для ориентированного и неориентированного графов. Это квадратная матрица порядка n, где n – число вершин, у которой

aij =

Матрицей инцидентности B = (bij) ориентированного графа называется матрица (n ´ m), где n – число вершин, m – число ребер, у которой

bij =

Для неориентированного графа матрица инцидентности B задается следующим образом:

bij =

Петле соответствует элемент, равный 2.

Пример.

Матрицы смежности и инцидентности графа, изображенного на рис. 3а, имеют вид (рис. 4):

.

Рис. 4

3. Для наглядности граф представляют в виде геометрического объекта: вершинам соответствуют различные выделенные точки в пространстве (на плоскости), ребрам – отрезки кривых, связывающие вершины.

Рассмотрим некоторые разновидности графов.

Неориентированный граф G = (V, E) – двудольный, если множество его вершин V можно разбить на два такие подмножества V 1 и V 2, что каждое ребро имеет один конец в V 1, а другой в V2. Если же каждая из вершин класса V1 связана ребром с каждой вершиной класса V2, то граф называется полным двудольным и обозначается Кm, n, где m =|V1|, n =|V2|. На рис. 5а изображен двудольный граф, на рис. 5б и 5в – полные двудольные графы К3,2 и К3,3 .

Пример.

а б в

Рис. 5

Полным графом называется граф без кратных ребер (и иногда без петель), в котором любые две вершины соединены ребром (ориентированным или неориентированным). Полный неориентированный граф с n вершинами обозначается Кn. Очевидно, граф Кn содержит n(n - 1)/2 ребер.

На рис. 6а, 6б и 6в изображены графы К3, К4, К5, соответственно. На рис. 6г также изображен полный граф.

а б в г

Рис. 6

5.3. Подграфы

Граф G¢ = (V¢, E¢) называется подграфом графа G = (V, Е), обозначение: G¢ Í G, если V¢ Í V, Е¢ Í Е и для множеств V' и Е' сохраняются инциденции графа G. При этом, очевидно, каждое ребро из Е' входит в подграф G¢ вместе со своими концами. Подграф называется собственным, если он отличен от самого графа.

Пример. Графы на рис. 7б и 7в являются подграфами графа на рис. 7а.

а б в

Рис. 7

5.4. Изоморфизм графов

Два графа G1 = (V1, E1) и G2 = (V2, E2) изоморфны, если между их вершинами существует взаимно однозначное соответствие j: V1 ® V2 такое, что для любой пары вершин u, v из V1 ребро (u, v) Î Е1 « ребро (j(u), j(v)) Î Е2.

Пример. Графы, изображенные на рис. 8, являются изоморфными.

Рис. 8

Изоморфные графы отличаются только нумерацией вершин. Матрицы смежности двух изоморфных графов могут быть получены одна из другой перестановкой строк и столбцов. Чтобы узнать, являются ли два графа изоморфными, нужно произвести все возможные перестановки строк и столбцов матрицы смежности одного из графов. Если после какой-нибудь перестановки получится матрица смежности второго графа, то эти графы изоморфны. Чтобы убедиться, что графы неизоморфны, надо выполнить все n! возможных перестановок строк и столбцов.

5.5. Степени вершин графа

Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v. Вершина графа, имеющая степень 0, называется изолированной, а степень 1 – висячей.

В случае неориентированного псевдографа считается, что вклад каждой петли, инцидентной некоторой вершине v, в d(v) равен 2 (тогда как вклад любого другого ребра, инцидентного вершине v, равен 1).

Полустепенью исхода (захода) вершины v орграфа D называется число d+(v) (d-(v)) дуг орграфа D, исходящих из вершины v (входящих в вершину v).

В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине v, в d(v) равен 1, как в d+(v), так и в d-(v).

Пример.

В графе G (рис. 3б) степень вершины v1 равна четырем, т. е. d(v1) = 4; вершина v4 – висячая, так как d(v4) = 1. В ориентированном псевдографе (рис. 3а) степень вершины v6 равна трем, т. е. d(v6) = d+(v6) + (d-(v6) = 2 + 1 = 3; вершина v1 – висячая, так как d(v1) = 1, вершина v5 – изолированная, так как d(v5) = 0.

Задания

Для аудиторных занятий

1. Даны реализации графов (рис. 9). Какие это графы? Описать их основные характеристики. Привести примеры элементов графов.

 

а) б) в)

Рис. 9

2. Записать матрицы смежности и инцидентности для неориентированного графа (рис. 9а).

3. Записать матрицы смежности и инцидентности для ориентированного графа (рис. 9б).

4. Изобразить ассоциированный граф для заданного графа (рис. 9б).

5. Изобразить все попарно неизоморфные 4-вершинные графы без петель и кратных ребер. Записать для них матрицы смежности и инцидентности.

6. Построить все попарно неизоморфные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин.

7. Какое из двух утверждений верно: а) ориентированный граф является частным случаем неориентированного графа; б) неориентированный граф является частным случаем ориентированного графа.

8. Перечислить все возможные способы задания графов.

9. Всегда ли матрица смежности симметрична относительно главной диагонали?

10. Как по матрице смежности определить число ребер неориентированного графа?

Для самостоятельной работы

1. Как по матрице инцидентности, не рисуя граф, определить его матрицу смежности?