Відносини на множинах і графи - студопедія

Кожен орієнтований граф G (X) визначає деякий від-носіння на безлічі X своїх вершин. Це ставлення може бути записано як xi G xj. Воно означає, що в графі є дуга, що йде від xi до xj.

Відношенню до властивості рефлексивності (x R х) повинна со-відповідати на графі петля в вершині. Якщо це ставлення з-блюдается у всіх вершинах х Î X, то відповідний граф G (X) повинен мати петлю в кожній своїй вершині.

У разі антіреф-лексівного відносини на мно-дружність X, відповідний граф ні в одній з вершин не має петлі.

Симетричної відношенню на безлічі X відповідає граф з неорієнтованими ребрами і, навпаки, граф з неорієнтованими ребрами визначає деякий симетрична відношення.

У разі антісімметріческого відносини на графі неможливе можна присутність двох дуг (xi. Xj), (xj. Xi) на графі, тобто сущест-вованіе неориентированного ребра. Крім того, на цих графах немає петель, тобто відповідне антісімметріческое ставлення антирефлексивне.

Ставлення, що володіє властивістю тотожності. відповід-ветствует графу з антисиметричних ставленням на множині вершин (орієнтованому графу) і додаванням петлі в кожній вершині. Цей граф не повинен мати контурів.

Мал. 3.18. Властивість транзи-ності на графі

Граф, відповідний транзитивних відношенню (рис. 3.18), має следующи-ми властивостями: для будь-якої пари орієнтованих ребер (дуг) графа (xi. Xj), (xj. Xk) є за-поневіряються дуга (xi. Xk). Можна сказати, що в графі, який відповідає транзитивних відношенню, для кожного шляху S (xi. Xk) є дуга (xi. Xk) (рис.3.19).

Мал. 3.19. Транзитивний (а) і нетранзитивність (б) графи

Ставлення, що володіє властивістю повноти. визна-лено на множині вершин повного орієнтованого графа.

Нульове відношення визначено на множині вершин нуль-графа.

Універсальне відношення визначено на множині вершин повного неорієнтованого графа з петлями. Додаткове до R відношення `R визначено на множині вершин додаткового графа Gd (Х) до G (X).

Графи, відповідні відношенню еквівалент-стрічок-ності. пред-являють собою сукупність компонент зв'язності (для кожного класу еквівалентності своя компонента) незв'язною графа. Кожна компонента незв'язною графа повинна бути повним неоріентіро-ванним графом з петлями (рис. 3.20).

Мал. 3.20. Граф, відповідний відношенню еквівалентності