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


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

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




Авто | Автоматизація | Архітектура | Астрономія | Аудит | Біологія | Будівництво | Бухгалтерія | Винахідництво | Виробництво | Військова справа | Генетика | Географія | Геологія | Господарство | Держава | Дім | Екологія | Економетрика | Економіка | Електроніка | Журналістика та ЗМІ | Зв'язок | Іноземні мови | Інформатика | Історія | Комп'ютери | Креслення | Кулінарія | Культура | Лексикологія | Література | Логіка | Маркетинг | Математика | Машинобудування | Медицина | Менеджмент | Метали і Зварювання | Механіка | Мистецтво | Музика | Населення | Освіта | Охорона безпеки життя | Охорона Праці | Педагогіка | Політика | Право | Програмування | Промисловість | Психологія | Радіо | Регилия | Соціологія | Спорт | Стандартизація | Технології | Торгівля | Туризм | Фізика | Фізіологія | Філософія | Фінанси | Хімія | Юриспунденкция

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

Загрузка...

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

Визначення. Граф Н називається частиною графу 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.003 сек.