Лекция 9 Отношения, графы Определения

Определение. Пусть а и b объекты. Через (а, b) обозначим упорядоченную пару, состоящую из объектов а и b, взятых в этом порядке. Упорядоченные пары (а, b) и (с, d) называются равными, если а = с и b = d. В противоположность этому {а, b}= {b, а}. Определение. Декартовым произведением множеств A и B, обозначаемым через АхВ, называют множество {(а, b) | а А и b B}. Пример. Пусть A = {1, 2} и В = {2, 3, 4}. Тогда AхB = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}

Отношения Определение. Пусть А и В множества. Отношением из А в В называется любое подмножество множества АхВ. Если А = B, то говорят, что отношение задано, или определено, на А (или просто, что это отношение на множестве A). Если R отношение из A в B и (а, b) R, то пишут аRb. A область определения отношения R, В множество его значений. Определение. Отношение {(b, а) | (а, b) R} называется обратным к отношению R и часто обозначается через R -1. B A AxBAxB R

Свойства отношений Определение. Пусть Aмножество и R отношение на A. Отношение R называется рефлексивным, если аRа для всех a из А, симметричным, если аRb влечет bRa для a и b из A, транзитивным, если аRb и bRс влекут аRс для а, b и с из A. Элементы а, b и с не обязаны быть различными. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. Важное свойство любого отношения эквивалентности R, определенного на множестве A, заключается в том, что оно разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности.

Графы Определение. Неупорядоченный граф G это пара (А, R), где А множество элементов, называемых вершинами (или узлами), а R отношение на множестве А. Если R несимметричное отношение, то G ориентированный граф; R симметричное, то G неориентированный граф. Пример. A={1, 2, 3, 4}, R = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}

Пара (а, b) R называется дугой (или ребром) графа G. Говорят, что дуга выходит из вершины а и входит в вершину b. Если (а, b) дуга, то говорят, что вершина а предшествует вершине b, а вершина b следует за вершиной a. Вершина b смежна с вершиной a. b a

Определения. Последовательность вершин (а 0, а 1,...,а n ), n1, называется путем (или маршрутом) длины n из вершины а 0 в вершину а n, если для каждого 1in существует дуга, выходящая из вершины а i-1 и входящая в вершину а i. Если существует путь из вершины а 0 в вершину а n, то говорят, что а n достижима из а 0. Циклом называется путь (а 0, а 1,...,а n ), в котором а 0 = а n. Граф называется сильно связным, если для любых двух разных вершин а и b существует путь из a в b (1, 2, 4,3) (1, 2, 3, 4, 1)

Степень вершины Степенью по входу (полустепенью входа) вершины а назовем число входящих в нее дуг, а степенью по выходу (полустепенью исхода) число выходящих из нее дуг. Если граф неориентированный, то степень вершины – это количество ребер, связанных с ней Для вершины 2: полустепень входа = 1 полустепень исхода = 2

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

Дуга и путь в ациклическом графе Если (a, b) – дуга в ациклическом графе, то a – прямой предок b, b – прямой потомок a. Если в ациклическом графе существует путь из a в b, то a – предок b, b – потомок a. b a

Матрица смежностей Пусть дан граф G= (V,E), N = |V|, M = |E|. Матрица смежностей для графа G – это матрица A размера NхN, состоящая из 0 и 1, в которой A[i, j]=1 тогда и только тогда, когда есть ребро из узла i в узел j

Матрица инцидентностей Матрица инцидентностей для графа G – это матрица B размера NхM, в которой : B[i, j]= 1, если ребро j инцидентно вершине i, -1, если ребро j входит в вершину i, 0, если ребро j не связано с вершиной i

Списки смежностей Списком смежностей для узла v называется список всех узлов w, смежных с v NULL

Табличное представление списков смежностей Номер вершиныСледующий

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