НОУ ІНТУІТ, Лекція, Види підграфів
Нехай дано граф G = (X, A), де X = i>, i = 1, 2, . n - безліч вершин, A = & lt; ai >, i = 1, 2, . m – безліч дуг.
Підграфом G'= (X', A') вихідного графа G називається такий граф G' для якого і . Приклади підграф показані на рис. 6.1, б, а вихідний граф - на рис. 6.1,а.
Основним підграфом Gp = (X, Ap) графа G називається граф, для якого. Таким чином, остовний підграф має те саме безліч вершин , що і вихідний граф G , але безліч дуг підграфа Gp є підмножиною безлічі дуг вихідного графа. Приклади остовних підграф наведено на рис. 6.1, ст. Для графа, що має m дуг, можна побудувати k остовних підграфів
Породженим підграфом Gs = (Xs, Гs) називається граф, для якого і для кожної вершини пряме відображення. Таким чином, породжений подграф складається з підмножини вершин Xs безлічі вершин вихідного графа і всіх таких дуг графа G, у якого кінцеві та початкові вершини належать підмножини Xs. Приклади породжених підграф наведено на рис. 6.1,г.
Як ілюстративний приклад розглянемо граф, вершини якого представляють співробітників певної установи, а дуги – лінії зв'язку між співробітниками. Тоді граф, що представляє тільки найважливіші зв'язки або канали зв'язку даної установи, є кістяком; граф , який докладно описує лінії зв'язку тільки якоїсь частини установи (наприклад, відділу), є породженим підграфом, а граф , який представляє лише важливі лінії зв'язку в межах відділу, є просто підграф.
Сильно зв'язкові графи та компоненти графа
Графи можуть бути класифіковані за зв'язністю: сильно зв'язкові, односторонньо зв'язкові, слабо зв'язкові та незв'язні.
Орграф називаєтьсясильно зв'язним , чи сильним , якщо двох будь-яких різних його вершин хi і xj існує, по крайнього заходу, один шлях , що з'єднує ці вершини. Це визначення також означає, що будь-які дві вершини сильно зв'язного графа взаємодосяжні. Приклад цього графа показано на рис. 6.2,а.
Орграф називається однобічно зв'язним , або одностороннім , якщо для будь-яких двох різних його вершин хi і xj існує, принаймні, один шлях з хi в xj або з xj в хi або обидва шляхи існують одночасно. Граф на рис. 6.2,б не є сильним, тому що в ньому немає шляху з х1 в х3 але є односторонньо зв'язковим.
Орграф називається слабко зв'язковим , чи слабким , якщо будь-яких двох різних вершин графа існує по крайнього заходу один маршрут , який з'єднує їх. Граф, зображений на рис. 6.2,в, не є ні сильним, ні одностороннім, оскільки в ньому не існує шляхів від х2 до х5 та від х5 до х2. Він слабко зв'язковий.
Орграф називається незв'язним , якщо деякої пари вершин орграфа немає маршруту, що з'єднує їх ( рис. 6.2, г).
За ознакою зв'язності може бути класифіковані і подграфы, але спочатку введемо поняття максимального подграфа. Нехай дано деяку властивість Р, яким можуть мати графи.
Максимальним підграфом графа G щодо властивості Р називається породжений підграф Gsm , що має цю властивість і таку, що не існує іншого породженого графа Gs , у якого і який так само має властивість Р . Так, наприклад, якщо як властивість Р взята сильна пов'язаність, то максимальним сильним підграфом графа G є сильний підграф , який не міститься в жодному іншому сильному підграфі. Такий підграф називається сильною компонентою графа. Аналогічно, одностороння компонента єодносторонній максимальний підграф, а слабка компонента – максимальний слабкий підграф.
Наприклад, у графі, наведеному на рис. 6.2,б, подграф, що складається з вершин 1, х4, х5, х6> є сильною компонентою графа. З іншого боку підграфи, що включають вершини 1, х6; та 1, х5, х6> , не є сильними компонентами (хоча і є сильними підграфами), оскільки вони містяться у графі, що складається з вершин 1, х4, х5, х6> і, отже, не максимальні. У графі, показаному на рис. 6.2,в, подграф не містить вершини 1, х4, х5, х6> є односторонньою компонентою.
У графі, наведеному на рис. 6.2,г, обидва подграфа, що включають вершини 1, х5, х6> та 2, х3, х4> є слабкими компонентами, і цей граф лише дві компоненти.
З визначень одразу ж випливає, що односторонні компоненти графа можуть мати загальні вершини. Сильна компонента повинна бути принаймні в одній односторонній компоненті, а одностороння компонента міститься в деякій слабкій компоненті даного графа.