2014-02-09
1050
Какими особенностями отличается граф G, взаимно однозначно соответствующий бинарному отношению R, если R:
а) симметрично;
б) антисимметрично;
в) рефлексивно;
г) антирефлексивно;
д) транзитивно.
Пусть бинарное отношение R определено на множестве V= {v1,...,vn }.
а) Симметричному отношению R взаимно однозначно соответствует неориентированный граф без кратных ребер G(R) в котором ребро (
) существует, если и только если выполнено 
(а значит, и 
в силу симметричности R).
б) Антисимметричному отношению R взаимно однозначно соответствует ориентированный граф без кратных ребер, не содержащий пар вершин с ребрами, противоположно направленными к разным вершинам.
в) Если R рефлексивно, то граф G(R) без кратных ребер имеет петли во всех вершинах.
г) Если R антирефлексивно, то граф G(R) без кратных ребер не имеет петель.
д) Если R транзитивно, то в графе G(R) без кратных ребер для каждой пары ребер () и (
) имеется замыкающее ребро (
).
