• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

Означення 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) входить в Г’ лише тоді, коли воно не входить в Г.

Читайте також:

1. Гомоморфізми та ізоморфізми алгебр
2. Де пнів більше – потрібно робити частковий обробіток грунту після часткового корчування пнів.
3. Ізоморфізм множин
4. Ізоморфізм та гомоморфізм алгебр
5. Ізоморфізм, гомоморфізм і двоїстість бінарних відношень
6. Поняття ізоморфізму
7. Поняття фі-феномену, гештальту ізоморфізму.
8. Приклади ізоморфізму алгебр.
9. Теорія ізоморфізму й ієрархії рівнів мови

Переглядів: 3300