Конечные и бесконечные множества. Мощность

Множества

Множества бывают конечные и бесконечные, счетные и несчетные. В конечном множестве число элементов конечно. Бесконечное множество содержит бесконечное число элементов.

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

Два множества Mи N,называются эквивалентными по мощности (обозначение M~N), если между их элементами можно установить биекцию.

Множество называется счетным, если оно эквивалентно множеству натуральных чисел.

Рассмотрим несколько примеров счетных множеств.

1. Множество всех целых чисел. Установим биекцию между множеством всех целых чисел и множеством всех натуральных чисел. Для этого расположим элементы этих множеств друг под другом попарно следующим образом

	-1		-2		-3		-4		.	.	.
									.	.	.

Этим самым биекция установлена, значит эквивалентность этих множеств доказана.

2. Множество всех рациональных чисел.Каждое рациональное число записывается однозначно в виде несократимой дроби: a=p/q, q>0. Назовем сумму +qвысотой рационального числа α. Число дробей с данной высотой конечно. Например, высоту 1 имеет только число 0/1. Высоту 2 - числа 1/1 и -1/1. высоту 3 - числа 2/1, 1/2, -2/1 и -1/2 и т.д. Будем нумеровать все рациональные числа по возрастанию высоты. При этом всякое рациональное число получит некоторый номер, т.е. будет установлена биекция между всеми натуральными и всеми рациональными числами.

Среди всех бесконечных множеств существуют такие, которые не являются счетными - это несчетные множества. Между счетным множеством и несчетным множеством биекцию провести нельзя, в последнем всегда элементов “больше”. Покажем, что множество действительных чисел, заключенных между нулем и единицей, несчетно.

Пусть множество P=[0,1] счетно, т.е. все точки этого отрезка можно последовательно пронумеровать: x₁,x₂,..., x_n,... Разделим отрезок [0,1] на три равных отрезка. Тогда по крайней мере один из отрезков не содержит точки x₁. Точка x₁ может принадлежать либо одному отрезку либо двум, если она лежит на их границе. Отрезок A₁, который не содержит точки x₁, снова разделим на три равных отрезка. По крайней мере один из них A₂ не содержит точки x₂. Отрезок A₂ который не содержит x₂, снова разделим на три равных отрезка и т.д. В результате получим последовательность вложенных один в другой отрезков A₁,A₂,..., A_n. Пусть x_k - точка, которая принадлежит всем этим отрезкам. Тогда, с одной стороны, x_kÎ[0,1] и в силу счетности точек отрезка входит в последовательность x₁,x₂,..., x_n,... С другой стороны, точка x_k не может совпасть ни с одной из точек этой последовательности, поскольку отрезки A₁, A_2… так построены, что ни одна из точек счетного множестваx₁,x₂,..., x_n,... им не принадлежит. Из этого следует, что принятое допущение о том, что множество P=[0,1]счетное неверно, т.е. множество несчетно.

Несчетные множества тоже можно сравнивать между собой путем построения биекции. Если биекцию удается построить, то этим самым доказывается эквивалентность множеств.

Рассмотрим примеры. Множества точек на любых двух отрезках эквивалентны между собой. На рис.4 показано, как можно установить биекцию между двумя различными отрезками abи cd.

Рис.4. Построение биекции между элементами множеств abи cd

Множество точек в интервале 0,1 эквивалентно множеству всех точек на прямой. Биекцию можно установить, например, с помощью функции

, -¥<x<¥, 0<y<1

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

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

Например, натуральных чисел оказывается “столько же” сколько и всех целых, сколько всех четных, нечетных, рациональных и т.д. На любом отрезке можно выделить часть его, а затем построить биекцию между отрезком и его частью, т.е. часть оказывается эквивалентной целому. Это свойство характерно для любого бесконечного множества. Мощность бесконечного множества точек на прямой называется мощностью континуума.

Пусть M- некоторое множество и пусть 2^m - множество - степень M. Тогда 2^m имеет мощность большую, чем мощность исходного множества M. Если рассмотреть множество-степень счетного множества, то оказывается, что его мощность равна мощности континуума. Для любого множества мощности континуума можно рассмотреть его множество-степень и мощность этого нового множества будет больше мощности континуума. Затем можно рассмотреть опять множество-степень этого нового множества и опять его мощность будет больше. Таким образом, не существует верхней границы мощности множеств, подобно тому как не существует “самого большого” числа.

Литература.

1. Коршунов Ю. М. Математические основы кибернетики: Учеб. пособие для вузов.- М.:Энергоатомиздат, 1987.- 496 с.;ил.

2. Сигорский В.П. Математический аппарат инженера.-К.: Техника, 1975-799с.:ил.

3. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа.- М.:Наука,1972.-495 с.;ил.

2.ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

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

Графом G(X,U)называется упорядоченная пара множеств: Xи UÍX². Элементы множества Xназываются вершинами графа, элементы множества U, представляющие собой пары {x_i, x_j}ÎUназываются ребрами графа, либо, если пары упорядочены (x_i, x_j)ÎU,то они называются дугами.

Геометрически граф можно представить в виде множества точек X={x₁, x₂,..., x_n} и множества линий, соединяющих эти точки. Точки представляют собой вершины графа, а линии, их соединяющие - ребра или дуги. Если указывается направление, то линии называются дугами, а граф называется ориентированным или направленным. Если направление не указывается, то линии называются ребрами, а граф - неориентированным (ненаправленным).

Граф определяет некоторое отношение между элементами множества X. То, что элемент x_jÎXнаходятся в отношении Г_ij к элементу x_iÎX,отображается на графе соединением элементов x_i и x_j линией (дугой или ребром).

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

x₁=Г₇₁x₇; x₄=Г₁₄x₁+Г₂₄x₂; x₈=Г₇₈x₇+Г₄₈x₄+Г₉₈x₉;

x₂=Г₁₂x₁+Г₅₂x₅; x₅=Г₈₅x₈+Г₂₅x₂; x₉=Г₈₉x₈.

x₃=Г₂₃x₂; x₆=Г₅₆x₅+Г₉₆x₉;

Рис.5. Ориентированный граф

В неориентированном графе для любых двух вершин x_i,x_jÎXсправедливо Г_ij= Г_ji.

Две вершины x_i,x_jÎXназываются смежными, если они определяют ребро (дугу).

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

Вершина x_i инцидента ребру (дуге) U_j,если она является началом или концом ребра (дуги) . Аналогично ребро (дуга)U_jинцидентно вершине x_j, если оно входит или выходит из этой вершины.

Число ребер (дуг) инцидентных некоторой вершинеx_j,называются степенью вершины и обозначают r(x_j). Для графа на рис.5 можно записать r(x₁)=3, r(x₂)=5 и т.д.

Вершину, неинцидентную никакому ребру (дуге), называют изолированной. Граф, состоящий только из изолированных вершин, называют нуль-графом и обозначают G₀.

Граф называют однородным степени t, если степени всех его вершин равны t.

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

Рис.6. Несвязный граф

Число, равное разности между числом вершин графа nи числом компонент связности P, называют рангом графа R(G)=n-P. На рис.6 n=13, P=3, R(G)=10.

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

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

Рис.7. Пример изоморфных графов

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

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

Рис.8. Примеры эйлеровых графов

Гамильгонов цикл - это цикл, который содержит все вершины графа, причем каждая вершина входит в цикл один раз. На рис.9 приведены примеры гамильтоновых графов, т.е. графов, содержащих гамильтоновы циклы

Рис.9. Примеры гамильтоновых графов

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

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

Рис.10. Задание графа таблицей

2. Матрицы графа. Различают несколько видов матриц графа:

Матрица смежности.Если задан граф G(X,U), то ему можно поставить в соответствие квадратную матрицу смежности

, n-число вершин графа.

Общий элемент матрицы для неориентированного графа равен

где m(x_i,x_j)-кратность ребер между вершинами x_iи x_j.

Для ориентированного графа общий элемент матрицы равен

На рис. 11а приведен пример неориентированного графа и его матрица смежности, а на рис.11б ориентированного графа и его матрицы смежности. Для неориентированного графа матрица смежности симметрична относительно главной диагонали. Кроме того, сумма единиц в каждом i-том столбце или строке соответствует степени вершины x_i.

Б)

Рис.11 а) Неориентированный граф и его матрица смежности;

б) Ориентированный граф и его матрица смежности.

Матрица инцидентности.Эта матрица представляет собой прямоугольную матрицу , n - число вершин, r - число ребер (дуг). Строки матрицы соответствуют вершинам, а столбцы - ребрам (дугам) графа G(X,U).

Эта матрица может быть записана как для ориентированного графа, так и для неориентированного. Для ориентированного графа, если k-ая ветвь заходит в i-ую вершину, то на пересечении i-ой строки и k-го столбца матрицы записывается +1. Если k-ая ветвь выходит из i-ой вершины, то на пересечении k-го столбца и i-ой строки записывается -1. Правильность составления матрицы легко проверить: число единиц в i-ой строке матрицы равно степени вершины x_i графа, а число единиц в каждом столбце - двум, т.к. каждое ребро (дуга) соединяет две вершины графа.

Матрица длин.Это квадратная матрица общий элемент которой равен

где - длина ребра (x_i, x_j).

Рис. 12. Граф и его матрица инцидентности

Над графами, также как и над множествами, можно выполнять операции объединения, пересечения, вычитания.

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

Объединение графов. Пусть заданы два графа G₁(X₁,Г₁) и G₂(X₂,Г₂).

Объединение этих двух графов G(X,Г) определяется следующим образом:

G(X,Г)=G₁(X₁,Г₁)ÈG₂(X₂,Г₂), при этом

X=X₁ÈX₂, "x_iÎX[Гx_i=Г₁x_iÈГ₂x_i],

т.е. отображение для каждой вершины графа G(X,Г) равно объединению отображений этой вершины для исходных графов. На рис. 13 показан пример объединения двух графов, где

X= X₁ÈX₂ = {x₁,x₂,x₃,x₄,x₅,x₆,x₇};

Гx₁ = Г₁x₁ÈГ₂x₁ = {x₂,x₅,x₃,x₇},

Гx₂ = Г₁x₂ÈГ₂x₂ = {x₁,x₃,x₅} и т.д.

Рис. 13. Объединение графов

Пересечение графов. G(X,Г)=G₁(X₁,Г₁)ÇG₂(X₂,Г₂). Вершинами графа G(X,Г) является пересечение вершин исходных графов: X=X₁ÇX₂. Отображение для каждой вершины графа G(X,Г) получается в результате пересечения отображений этой вершины для исходных графов: "x_iÎX[Гx_i=Г₁x_iÇГ₂x_i]. (см. рис. 14).

Рис. 14. Пересечение графов

X=X₁ÇX₂={x₁,x₃,x₄},

Гx₁=Г₁x₁ÇГ₂x₁={x₃} и т.д.

Вычитание графов. G(X,Г)=G₁(X₁,Г₁)\G₂(X₂,Г₂). Вершинами графа G(X,Г) является вершины графа G₁(X₁,Г₁), за исключением вершин, общих для исходных графов: X=X₁\X₂.

Отображение для каждой вершины графа G(X,Г) является пересечение множества вершин этого графа и отображения той же вершины в графе G₁(X₁,Г₁):

"x_iÎX[Гx_i=XÇГ₁x_i].

В примере на рис. 15 X=X₁\X₂={x₂,x₅}; Гx₂=XÇГ₁x₂={x₅}и т.д.

Рис. 15. Вычитание графов