Бинарные отношения на мн-ве. Граф отношений

Вопрос 1

Взаимно-однозначные соответствия

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

Рисунок

См. прошлую сессию, последний вопрос

Вопрос 2

Бинарные отношения на мн-ве. Граф отношений.

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

Если , то говорят, что задано на множестве .

Пример 1. Пусть и . Тогда подмножество в является бинарным отношением между множествами и

Пример 2. На множестве целых чисел отношение делимости, состоящее из упорядоченных пар , в которых делится на , является бинарным отношением. В этом случае обозначение заменяется на .

Пример 3. На множестве действительных чисел упорядочение является бинарным отношением на , состоящим из всех точек плоскости , лежащих не ниже прямой .

Подмножества множества пар – бинарное отношение.

1 2 3 4 …

1(1;1) (1;2) (1;3)… (2;7) (3;9)

2..

3...

..

Граф отношений – набор точек, некоторые из которых соединены линией. Точки – вершина графа, отрезки – ребра.

Граф – математический объект, состоящий их мн-ва вершин и ребер.

1 2 Смежные вершины

4 3 Смежные ребра

Число ребер, выходящих из вершины – степень вершины.

d (1)=1 – висячая

d(2)=3

d(3)=2

d(4)=2

d(5)=0 – изолированная вершина

Два графа G, H назыв. изолированными, если можно пронумеровать вершины каждого из них. Если две вершины будут смежными в одном из графов, то вершины с такими же номерами будут смежными и во втором. Пишут, что графы равны: G=H

1 2 3

4 5 6

Полный граф – любая вершина соединена ребром. К_n

К₁ К₂ Колич. вершин:

Связный граф – две любые вершины могут быть соединены путем из ребер.

Несвязный граф состоит из кусков, каждый из которых – связь (дороги, маршруты)

Планарный граф – ребра не пересекаются

Уникурсальный граф можно нарисовать одним росчерком карандаша.