Ізоморфізм графів. Підграф. Суграф. Частковий граф

Нехай і – графи і – взаємно однозначна відповідність.

Означення 2.1.5. Відображення називають ізоморфізмом графів і , якщо для довільних вершин і графа їх образи і суміжні у графі тоді і тільки тоді, коли і суміжні в .

Якщо таке відображення існує, то графи і називають ізоморфними. Відношення ізоморфізму графів є відношенням еквівалентності.

Означення 2.1.6. Підграфом G ’(X ’, Г ’) графа G (X, Г) називають граф, у якого Х ’Ì Х, Г ’= Г Ç(Х ´ Х ´ N), тобто ребро (x _i, x _j) міститься в Г ’ лише тоді, якщо x _i та x _j містяться в Х ’, граф G називається надграфом графа G ’.

Означення 2.1.7. Якщо всі вершини Х ’= Х графа G присутні у підграфі G ’, то G ’ називають остовним підграфом G або суграфом.

Означення 2.1.8. Частковим графом G ’(X ’, Г ’) графа G (X, Г) називають граф, у якого Х ’Ì Х, Г ’Ì Г.

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

Наприклад:

Якщо множина вершин Х ’ графа G ’ є найменшою підмножиною Х, що містить всі кінцеві вершини ребер в Г ’, то підграф G ’ називають реберно породженим підграфом графа G і позначують .

Якщо множина ребер Г ’ графа G ’ є найбільшою підмножиною Г такою, що кінцеві вершини всіх його ребер належать Х ’, то G ’ називають вершинно породженим підграфом графа G.

Означення 2.1.9. Граф називають доповненням простого графа G =(Х, Г) якщо ребро (x _i, x _j) входить в Г ’ лише тоді, коли воно не входить в Г.

Дата добавления: 2014-10-17