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

Компоненти зв’язності

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

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

Означення 2.3.1. Компонента зв’язності чи просто компонента – це підграф, породжений множиною типу або вершинно породжений підграф .

Розглянемо незв’язний неорієнтований граф .

Множину його вершин можна розбити на такі підмножини:

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

Очевидно, виконуються такі властивості для підмножин , які утоворюють розбитття множини :

1) ;

2) ;

3) .

Підграфи , , – компоненти зв’язності графа . Кожен з них – максимально зв’язний підграф графа , тобто не є власним підграфом будь-якого іншого підграфа .

Отже, наведений на прикладі граф має три компоненти зв’язності.

Теорема 2.3.1. Граф буде зв’язним лише у тому випадку, якщо він складається з однієї компоненти зв’язності.

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

1. Активні компоненти – електронні прилади
2. Гіпотези, які не відхиляються в експерименті, перетворюються на компоненти теоретичного знання про реальність: факти, закономір­ності, закони.
3. Головні етапи розробки програми соціологічного дослідження та її компоненти.
4. Головні компоненти біологічного фактора
5. Гумусові компоненти ґрунту
6. Електричні компоненти віртуальної лабораторії
7. Елементи й компоненти ландшафту
8. Етапи і компоненти системного аналізу.
9. Зміст і компоненти стратегічного управління навчальним закладом
10. ЗМІСТ РИТОРИКИ, СУТНІСТЬ І КОМПОНЕНТИ ПОНЯТТЯ «РИТОРИЧНА ФОРМУЛА»
11. Зовнішньоекономічна політика України та її компоненти.
12. Кожна теорія включає в себе певні компоненти.

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