Пример 3.

Какими особенностями отличается граф G, взаимно однозначно соответствующий бинарному отношению R, если R:

а) симметрично;

б) антисимметрично;

в) рефлексивно;

г) антирефлексивно;

д) транзитивно.

Пусть бинарное отношение R определено на множестве V= {v₁,... ,v_n }.

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

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

в) Если R рефлексивно, то граф G(R) без кратных ребер имеет петли во всех вершинах.

г) Если R антирефлексивно, то граф G(R) без кратных ребер не имеет петель.

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