Студопедия
Контакти
 


Тлумачний словник

Реклама: Настойка восковой моли




Частини, суграфи і підграфи графу.

Операції з частинами графу

Визначення. Граф Н називається частиною графу G (позначається H Í G), якщо:

а) V(H) Í V(G);

б) E(H) Í E(G).

Визначення. Граф Н називається суграфом графу G, якщо він є частиною графу G і

V(H) = V(G).

На Рис. 4 зображені граф G і його три частини. Граф H3 є суграфом.

 

Рис.4.

 

Визначення. Суграф H називається покриваючим для графу G, якщо будь-яка вершина H інцидентна хоча б одному ребру з G. Зауважимо, що якщо в графі G є ізольовані вершини, то для нього не існує покриваючого графу H.

Визначення. Підграфом G(U) графу G(V) називається така його частина, яка містить всі ребра графу G(V), що з’єднують дві будь-які вершини з множини U.

На рис. 4 H1 не є підграфом G (не містить ребро e(2, 4)), а H2 – підграф графу G.

Визначення. Зірковим графом, який визначається деякою вершиною a Î V, називається граф, що містить всі ребра даного графу G(V), інцидентні вершині „a”.

За аналогією з операціями поміж множинами можна виконувати і операції між графами.

Визначення. Якщо H – частина графу, то (доповнення графу H) – це граф, в який входять всі ребра графу G, які не належать H:

.

Визначення. Нехай H1 і H2 - дві частини графу G. Тоді H = H1 È H2 (об’єднання або сума) це також частина графу G, яка складається зі всіх ребер, що належать або H1 або H2.

Визначення. Нехай H1 і H2 - дві частини графу G. Тоді H = H1 Ç H2 (перетин) це частина графу G, яка складається зі всіх ребер, що належать H1 та H2 одночасно.

Визначення. Якщо дві частини H1 і H2 графу G не мають спільних вершин, то їх сума H = H1 È H2 називається прямою. Якщо H1 і H2 не перетинаються по ребрах, то їх сума називається прямою по ребрах.

Наприклад: - пряма сума за ребрами.

 


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

  1. Система оплати праці характеризує взаємозв’язки елементів заробітної плати: тарифної частини, доплат, надбавок і премій.
  2. Храм, його складові частини, їх значення

Загрузка...



<== попередня сторінка | наступна сторінка ==>
Степінь вершини графа | Деякі визначення

Не знайшли потрібну інформацію? Скористайтесь пошуком google:


 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.001 сек.