Задание 2. Определите свойства отношения

Определите свойства отношения. Отношение задано на множестве действительных чисел R.

Варианты

1. R={(x, y)| x, y Î R и x - y <0}.

2. R={(x, y)| x, y Î R и x + y £ 0}.

3. R={(x, y)| x, y Î R и x = y }.

4. R={(x, y)| x, y Î R и x = y ²}.

5. R={(x, y)| x, y Î R и x ² = y }.

6. R={(x, y)| x, y Î R и | x – y | £ 3}.

7. R={(x, y)| x, y Î R и x ³ = y }.

8. R={(x, y)| x, y Î R и x = y ³}.

9. R={(x, y)| x, y Î R и x +5>3 – y }.

10. R={(x, y)| x, y Î R и | x | ³| y |}.

11. R={(x, y)| x, y Î R и x ² = y ²}.

12. R={(x, y)| x, y Î R и x > y ²}.

13. R={(x, y)| x, y Î R и x ³ = y ³}.

14. R={(x, y)| x, y Î R и x £ y +1}.

15. R={(x, y)| x, y Î R и x ² + y ²=1}.

16. R={(x, y)| x, y Î R и x £ y }.

17. R={(x, y)| x, y Î R и x £2 y }.

18. R={(x, y)| x, y Î R и x +2£ y +1}.

19. R={(x, y)| x, y Î R и x -5£ y +3}.

20. R={(x, y)| x, y Î R и 2 x ³3 y }.

Задание 3

Для отношения, заданного матрицей, определить является ли оно отношением эквивалентности. Если является, то определить классы эквивалентности.

Варианты

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

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

Теоретические сведения

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

Пусть задано некоторое конечное множество X, элементы которого будем называть вершинами, и множество V, состоящее из пар элементов (x _i, x _j) множества X. Упорядоченная пара множеств G=(X,V ) называется графом. Вершины изображаются точками, а пары элементов – линиями, соединяющими точки, соответствующие образующим пары вершинам [3, 4, 5, 6].

Если в определении графа существенно в каком порядке выбираются вершины (то есть пара (x _i, x _j) отлична от пары (x _j, x _i)), то такой граф называют ориентированным илиорграфом, а пару (x _i, x _j) - дугой, при этом считается, что х _i - начальная вершина, a x _j - конечная. В геометрической интерпретации дуге соответствует направленный отрезок. Часто орграф задают парой G=(X, Г), где Х - множество вершин, а Г - неоднозначное отображение, ставящее в соответствие каждой вершине подмножество в X. Г(х _i) - множество вершин х _jÎ Х, для которых в графе G существует дуга (х _i, х _j). Г^l(х _i) - множество вершин х _jÎ X, для которых в графе G существует дуга (x _j, х _i).

Если в определении графа не существенен порядок вершин при образовании пары (х _i, x _j), то граф называют неориентированным или неорграфом, а пару (x _i, x _j) - ребром.

Рис. 1 Рис. 2

Путем в графе G называется такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей. Для неорграфа такая последовательность ребер называется цепью. Если путь (цепь) проходит через вершины х ₁,..., х _k то будем обозначать его (ее) символом [ x ₁, …, x _k].

Для графа на рис. 2 последовательность дуг (x₁, x₂), (x₂, x₄), (x₄, x₃) является путем и может быть обозначена следующим образом [ x₁, x₂, x₄, x₃ ]. Для графа на рис. 3 цепью является, например, следующая последовательность ребер (x₂, x₃), (x₃, x₅), (x₅, x₄), которую обозначим через [ x₂, x₃, x₅, x₄ ].

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

Путь (цепь), у которого(-ой) начальная и конечная вершина совпадают, называется контуром (циклом). Для графа на рис. 3 циклом является, например, следующая цепь [ x₂, x₃, x₅, x₁, x₂ ].

Простым циклом графа называется цикл, в котором все вершины различны за исключением начальной и конечной вершины, которые совпадают. Например, для графа на рис. 3 цикл [ x₂, x₃, x₅, x₁, x₂ ] является простым, а цикл [ x₂, x₃, x₄, x₅, x₃, x₁, x₂ ] не является простым.

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

Две вершины х _i и х _j называются смежными, если существует соединяющее их ребро (дуга), при этом вершины называются инцидентными этому ребру (дуге), а ребро (дуга) – инцидентным(-ой) этим вершинам. Аналогично, два различных ребра (дуги) называются смежными, если они имеют по крайней мере одну общую вершину.

Вершины х ₁ и х ₄ смежны (рис. 2.), дуга (х ₁, х ₄) инцидентна вершинам х ₁ и х ₄, а вершины х ₁ и х ₄ инцидентны дуге (х ₁, х ₄). Ребра (х ₁, х ₃) и (х ₃, х ₄) смежны (рис. 3).

Число дуг, исходящих из вершины х _i ориентированного графа, называется полустепенью исхода вершины х _i и обозначается . Число дуг, заходящих в вершину х _i ориентированного графа, называется полустепенью захода вершины х _i и обозначается . Так, для орграфа, представленного на рис.2 , .

В неориентированном графе число ребер, инцидентных данной вершине х _i, называют степенью вершины х _i и обозначают d(х _i). Вершина графа, имеющая степень 0, называется изолированной, а вершина, имеющая степень 1 – висячей. Для неорграфа на рис. 3 d(х ₁)=3, d(х ₃)=4.

Информация о структуре графа может быть задана матрицей смежности. Матрицей смежности графа G=(X,V), | X|=n называется квадратная матрица , элементы которой определяются следующим образом:

Замечание. Матрица смежности неориентированного графа симметрична. В случае кратных ребер a_ij есть количество ребер, соединяющих вершины x_i и x_j. Для орграфа а_ij определяется как количество дуг, направленных от вершины x_i к вершине x_j.

Матрицей инцидентности графа G=(X,V), |Х|=п,|V|=m называется матрица , элементы которой определяются следующим образом:

если G - неориентированный граф, то

Замечание. Для ориентированного графа петлю, т. е. дугу вида (х_i, х_i) удобно представлять иным значением в строке х_i, например, 2.

Пример. Матричные представления графов проиллюстрированы на рис. 3, 4.

			(1,2)	(1,3)	(3,2)	(3,4)	(5,4)	(5,6)	(6,5)
			-1		-1
В =				-1
						-1	-1
									-1
								-1

Рис. 3

а) ориентированный граф и его матрица инцидентности,

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

Рис. 4. Матрицы смежности для графов на рис. 3

Понятия связности и достижимости. Если в графе существует путь, идущий от вершины x_i к вершине х_j, то говорят, что вершина x_jдостижима из вершины х_i.

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

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

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

Пример. Граф, приведенный на рис. 5(а) является сильно связный. Граф, показанный на рис. 5(б), не является сильным, так как в нем нет пути из x ₅ в x₂. Граф, приведен­ный на рис. 6, является несвязным.

Максимальный по включению сильно связный подграф данного графа называется его сильной компонентой связности (СК).

а) б)

Рис. 5. Сильно связный граф (а), граф, не являющийся сильным графом (б)

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

Например, в графе G, приведенном на рис. 5(б), подграф ({ х ₁, x ₄, х ₅, х₆}) является сильной компонентой графа G. С другой стороны, подграфы ({ х ₁, х ₆}) и ({ х ₁, х ₅, х ₆}) не являются сильными компонентами, хотя и являются сильными подграфами, поскольку они содержатся в графе ({ х ₁, x ₄, x ₅, х ₆}) и, следова­тельно, не максимальные.

Максимальный связный подграф неориентированного графа G называется компонентой связности.

Матрица достижимостей графа G =(X, V) , определяется следующим образом:

Множество вершин R (x _i) графа G, достижимых из заданной вершины x_i, состоит из таких элементов x_j, для которых (i, j)-й элемент в матрице достижимостей равен 1.

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

Поскольку Г(x_i) является множеством таких вершин x_j, которые достижимы из x_i c использованием путей длины 1 (т.е. Г(x_i) – такое множество вершин, для которых в графе суще­ствуют дуги (x_i, x_j)) и поскольку Г(x_j) является множеством вершин, достижимых из x_j с помощью путей длины 1, то множество Г(Г(x_i))=Г²(x_i) состоит из вершин, достижимых из x_i c использованием путей длины 2. Аналогично Г^p(x_i) является множеством вершин, которые достижимы из x_i с помощью путей длины р.

Так как любая вершина графа G, которая достижима из x_i, должна быть достижима с использованием пути (или путей) дли­ны 0, или 1, или 2,..., или р (с некоторым конечным р≤n), то множество вершин, достижимых из x_i, можно представить в виде

R (x_i) = { x_i }ÈГ(x_i)È Г² (x_i)È…È Г^p (x_i) (1)

Таким образом, множество R (x_i) может быть получено последова­тельным выполнением (слева направо) операций объединения в соотношении (1), до тех пор, пока «текущее» множество не перестанет изменяться при очередной операции объединения. С этого момента последующие операции не будут давать новых элементов множеству и, таким образом, будет получено, достижимое множество R (x_i). Число объединений, которое нужно выполнить, зависит от графа, но, очевидно, что число р меньше числа вершин в графе.

Матрицу достижимостей можно построить так. Находим достижимые множества R (x_i) для всех вершин x_i Î Х способом, приведенным выше. Положим r_ij =1, если x_j Î R (x_i), и r_ij =0 в противном случае. Матрица контрдостижимостей (матрица обратных достижимостей) , определяется следующим образом:

Контрдостижимым множеством Q (x_i) графа G является множество таких вершин, что из любой вершины этого множества можно достигнуть вершину x _i.

Из определений очевидно, что столбец x _i матрицы Q (в котором q_ij= 1, если x_i Î Q (x _i), и q_ij =0 в противном случае) совпадает со строкой x _i матрицы R, т. е. Q = R ^T, где R ^T – матрица, транспонированная к матрице достижимостей R.

Поиск по сайту: