- •Г.И. Коротеев дискретная математика элементы тории множеств, отношений, графов, алгоритмов и булевых функций
- •Пример 1.1
- •Пример 1.2
- •Пример 1.3
- •Пример 1.4
- •Пример 1.5
- •Пример 1.6
- •Пример 1.7
- •Пример 1.8
- •Пример 1.9
- •Пример 1.12
- •Пример 1.13
- •Пример 1.15
- •Пример 1.16
- •Пример 1.17
- •Пример 1.18
- •Пример 1.19
- •Пример 1.20
- •Пример 1.21
- •Пример 1.22
- •Пример 1.23
- •Пример 1.25
- •1. Пусть (p,п) и (f,п) – множества упорядоченные по отношению п из примера 1.21. Диаграммы Хассе этих множеств представлены на рис. 1.6 и 1.7.
- •Пример 1.26
- •Пример 1. 27
- •Бинарная алгебраическая операция
- •Пример 1.28
- •Свойства, терминология
- •Пример 1.29
- •Пример 1.30
- •Пример 1.31
- •Пример 2.1
- •Пример 2.2
- •Пример 2.3
- •Пример 2.4
- •Пример 2.5
- •Пример 2.6
- •Пример 2.7
- •Пример 2.8
- •Пример 2.9
- •Пример 2.10
- •Пример 2.12
- •Пример 2.13
- •Пример 2.14
- •Доказательство
- •Пример 2.15
- •Пример 3.1
- •Пример 3.2
Пример 1.31
1. На множестве матриц порядка n нейтральным элементом относительно операции умножения матриц является единичная матрица.
2. На множестве целых чисел нейтральным элементом относительно операции умножения будет число 1, а относительно операции сложения – число 0. В этом случае он так же называется нулевым элементом.
3. На множестве целых четных чисел относительно операции умножения единичного элемента нет.
Утверждение 1.11. Единичный элемент единственен.
Предположим, что на множестве M относительно операции умножения имеются два единичных элемента e и e', причем e e'. Тогда, по определению единичного элемента e, имеем e'e = ee' = e, а по определению единичного элемента e', имеем: ee' = e'e = e'. Следовательно, e' = e. Полученное противоречие и доказывает данное утверждение.
Степени
Пусть а1 = а2 =…= an = a. Тогда произведение ааа..а (n раз) называется n-й степенью элемента а и обозначается: an, где n = 1, 2, … Если М имеет единичный элемент, то полагаем: a0 = e.
Из теоремы 1.1 имеем:
аа…а = (аа…а)(аа…а)
n – раз m – раз k – раз,
отсюда, с одной стороны, an = amak , c другой стороны, an = am+k, т.е. am+k = amak. Доказать самостоятельно, что (as)t = ast, где s, k, t, m N, N – множество натуральных чисел.
В аддитивной терминологии понятию степени соответствует кратность:
а+а+…+а = na
n – раз.
Аналогично можно доказать равенства:
ma + ka = (l + k)a; s(ta) = (st)a, где m, k, s, t N.
2. ГРАФЫ
2.1. Основные понятия
Графы их вершины, ребра и дуги
Изображение графов
Матрицы инцидентности
Матрицы смежности
Идентификация графов
Графы без кратных ребер и изолированных вершин
Степени вершин графа. Однородные графы.
Подграфы, дополнения
Операции на графах
Графы, их вершины, ребра и дуги
Теорию графов начали интенсивно разрабатывать с решения некоторых задач о геометрических конфигурациях, состоящих из точек и линий. В этих задачах важным было то, что некоторые две точки соединены друг с другом, и то, что каждая линия соединяет какие-либо две из заданных точек, длина же и тип линии несущественны, как и другие геометрические характеристики конфигурации.
Приведем ряд определений теории графов.
Графом G называется совокупность множеств (V, E), между элементами которых определено отношение инцидентности, причем каждый элемент e E инцидентен одной и только одной неупорядоченной паре {v, w} элементов из V. При этом говорят, что e соединяет v, w и обозначают v w, или c указанием графа G: v G w. Элементы множества V называются вершинами графа G. Элементы множества E – его ребрами Если v w, то говорят, что вершины v и w связаны отношением непосредственной достижимости.
Ориентированным графом (орграфом) D называется совокупность множеств (V, E), между элементами которых определено отношение инцидентности, причем каждый элемент e E инцидентен одной и только одной упорядоченной паре (v, w) элементов из V. При этом говорят, что e ведет из v в w и обозначают v w, или c указанием графа G: v G w . Элементы множества V называются вершинами графа D. Элементы множества E – его дугами. Если v w, то говорят, что вершины v и w связаны отношением непосредственной достижимости. Говорят также, что первая в упорядоченной паре (v, w) вершина – начало, а вторая – конец дуги e, и то, что дуга e исходит из начала v и заходит в конец w.
Две вершины в графе (орграфе) называются смежными, если они инцидентны одному и тому же ребру (дуге). Множество вершин смежных с вершиной v неориентированного графа обозначается как (v) = {x | x v}. В ориентированном графе множество +(v) = {x | v x} называют множеством преемников вершины v, а множество –(v) = {x | x v} – множеством предшественников вершины v. Если в графе (орграфе) G вершины s и t несмежны, то будем использовать обозначения s ›–‹G t или s ›–‹ t.
Вершины и ребра (дуги) графа G (орграфа D) иначе называют его элементами, и вместо v V и e E пишут, соответственно, v G и e G (v D и e D).
Граф называется нуль-графом, если множество его вершин V = (а, следовательно, и E = ). Граф называется пустым графом, если множество его ребер
E = . Граф называется полным, если каждой паре различных вершин из V инцидентно одно и только одно ребро (полный n-вершинный граф обозначают Kn).
Граф, содержащий кратные ребра (инцидентные одной паре вершин), называется мультиграфом. Граф, содержащий петли (ребра, концами которых является одна и та же вершина), называется псевдографом. Иначе он называется простым графом.
Аналогичные определения имеют место и для ориентированных графов.
Понятие графа применяется, в частности, при анализе функционирования систем. Компоненты изучаемой системы моделируют вершинами графа, а пары взаимодействующих компонент – его ребрами. Такой граф называют структурным графом системы.
Из приведенных определений следует, что задать граф (орграф), значит, описать тем или иным способом множества его вершин и ребер (дуг), а также задать отношение инцидентности. Когда граф G (орграф D) – конечный, его можно, в частности, задать (изобразить) графически. Рассмотрим некоторые из способов задания графов (орграфов).
Изображение графов
Граф может быть задан графически, или изображен с целью иллюстрации некоторых его свойств. Графическое изображение графов состоит из точек (вершин) и линий (ребер) или линий со стрелками (дуг) для ориентированных графов. На рис. 2.1. приведены примеры изображений некоторых графов:
Рис. 2.1. Изображение графов
а) – полный граф, K5;
б) – орграф;
в) – граф с пустым множеством ребер E (пустой граф);
г) – граф, в котором линии, изображающие ребра, пересекаются;
д) – псевдограф (имеется ребро в виде петли) и мультиграф (имеются кратные ребра);
е) – бесконечный граф.
Здесь мы будем рассматривать только конечные графы.
|
|
|
Рис. 2.2. Ориентированные графы
При изображении ориентированных графов (рис. 2.1,б) направления дуг отмечаются линиями со стрелками, при этом стрелка на дуге может располагаться в любом месте. Так, на рисунке 2.2,а изображен ориентированный мультиграф, а на рисунке 2.2,б – ориентированный псевдограф, здесь направление обхода петли роли не играет.
Каждому неориентированному графу можно поставить в соответствие ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя дугами, инцидентными тем же вершинам, и имеющими противоположные направления. Такое соответствие называется каноническим (рис. 2.3).
Рис. 2.3. Каноническое соответствие графов
Неориентированный граф G = (V,E) называется ассоциированным с ориентированным графом D = (V, X), если его множество вершин совпадает с множеством вершин ориентированного графа G, а ребро e инцидентное паре вершин {u, v} существует тогда и только тогда, когда u ≠ v и имеется дуга из u в v или из v в u. Т.е. множество E = {e={u,v}| ((u, v) X или (v, u) X), u ≠ v } (рис. 2.4).
Рис. 2.4. Граф G ассоциирован с графом D
Матрицы инцидентности
Если вершины и ребра (дуги) графа (орграфа) занумерованы (помечены), соответствующие множества имеют вид: V = {v1, v2, …,vn }; E = {e1, e2, …,em}, то отношение инцидентности можно определить матрицей, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки – ребрам (дугам).
Матрицей инцидентности графа G с n вершинами и m ребрами называется матрица B(G) = { bij } размерности m n, элементы которой определяются по формулам:
Матрицей инцидентности орграфа D с n вершинами и m дугами называется матрица B(D) = { bij } размерности m n, элементы которой определяются по формулам:
Если ориентированный граф содержит петлю, то в соответствующее место матрицы D ставится произвольное число отличное от –1, 0 или 1.