Відношення порядку і відношення еквівалентності на графі

Із зазначених вище властивостей очевидно, що граф дає зручне геометричне уявлення відношень на множині, тому теорія графів і теорія відношень на множині взаємно доповнюють одна одну.

Будемо вважати, що на графі G=(X, Г) введене відношення порядку, якщо для будь-яких 2-х вершин (х і у), що задовольняють умові х £ у, існує шлях із х в у. У цьому випадку говорять, що вершина х передує вершині у.

Покажемо, що дане визначення відбиває на графі усі властивості відношення порядку.

Рефлексивність. Умова х £ х означає еквівалентність вершини самої собі, тобто умова хºх. Проте при бажанні цю умову можна розглядати як наявність шляху з х в х, тобто як петлю у вершині х (рис. 2.9, а).

Транзитивність. Умова х£у, у£z ®х£z означає, що вершини x, y, z послідовно зустрічаються на тому самому шляху (рис. 2.9, б).

Рис.2.9. Властивості відношень на графах

Антисиметричність. Покажемо справедливість умови х£у, у£х ®хºу. Ліва частина цього виразу говорить про те, що існує шлях із х в у, а так само існує шлях з у в х. Але це означає, що в графі є контур, на якому лежать вершини х і у (рис.2.9, в).

З правої частини умови випливає, що вершини, які лежать на тому самому контурі, є еквівалентними. Будемо розглядати цей висновок як визначення еквівалентності на графі і покажемо, що таке визначення задовольняє всім умовам відношення еквівалентності. Умови рефлексивності хºх і симетрії хºу®уºх є очевидними і випливають із даного вище визначення еквівалентності. Умова транзитивності хºy, yºz®xºz також є очевидним, тому що говорить про те, що якщо в графі є контур з вершинами X і Y, а також контур з вершинами у і z , то є і контур, на якому лежать вершини х і z.

Таким чином, відношення порядку разом із відношенням еквівалентності визначає деякий граф.

На графі може бути також уведене відношення суворого порядку. У цьому випадку для будь-яких двох вершин (X і Y), що задовольняють умові X<Y, існує шлях, що йде з X у Y. Умова транзитивності X<Y<Z®X<Z означає, як і в попередньому випадку, що вершини X, Y і Z зустрічаються послідовно на тому самому шляху. Умова антирефлексивності (X<X хибно) говорить про відсутність петель на графі, а умова несиметричності (X<Y, у<d) - про відсутність контурів.

Таким чином, відношення суворого порядку визначає граф без контурів.

Зводимо всі дані по відношенню порядку в табл. 2.1.

Таблиця 2.1.

Визначення різноманітних видів порядку