Анотація: Розглядаються підграфи такі як кістяк, породжений і різні види подграфов по зв'язності. Мета лекції: Дати уявлення про види подграфов і їх властивості.
Нехай дано граф G = (X, A), де X = {хi}, i = 1, 2, ..., n - безліч вершин, A = {ai}, i = 1, 2, ..., m - безліч дуг.
Подграфом G '= (X', A ') вихідного графа G називається такий граф G', для якого 
і 
. Приклади подграфов показані на Мал. 6.1 , Б, а вихідний граф - на Мал. 6.1 , А.
Мал.6.1.
Види подграфов: а - вихідний граф; б - підграфи; в - остовне підграфи; г - породжені підграфи
Остовне подграфом Gp = (X, Ap) графа G називається граф, для якого 
. Таким чином, кістяк підграф має те ж саме безліч вершин, що і вихідний граф G, але безліч дуг подграфа Gp є підмножиною множини дуг вихідного графа. Приклади остовних подграфов наведені на Мал. 6.1 , В. Для графа, що має m дуг, можна побудувати k остовних подграфов
k = C1m + C2m + ... + Cm-1m = 2m-1
Породженим подграфом Gs = (Xs, Гs) називається граф, для якого 
і для кожної вершини 
пряме відображення 
. Таким чином, породжений підграф складається з підмножини вершин Xs безлічі вершин вихідного графа і всіх таких дуг графа G, у якого кінцеві і початкові вершини належать підмножині Xs. Приклади породжених подграфов наведені на Мал. 6.1 , Г.
Як ілюстративний приклад розглянемо граф, вершини якого представляють співробітників деякого установи, а дуги - лінії зв'язку між співробітниками. Тоді граф, що представляє тільки найбільш важливі зв'язки або канали зв'язку даної установи, є остовне подграфом; граф, який детально описує лінії зв'язку тільки якоїсь частини установи (наприклад, відділу), є породженим подграфом, а граф, який представляє тільки важливі лінії зв'язку в межах відділу, є просто подграфом.
Сильно зв'язкові графи і компоненти графа
Графи можуть бути класифіковані по зв'язності: сильно зв'язкові, односторонньо зв'язкові, слабо зв'язкові і незв'язні.
Орграф називається сильно зв'язковим, або сильним, якщо для двох будь-яких різних його вершин хi і xj існує, принаймні, один шлях, що з'єднує ці вершини. Це визначення означає також, що будь-які дві вершини сильно зв'язного графа взаімодостіжіми. Приклад даного графа показаний на Мал. 6.2 , А.
Мал.6.2.
Види графів по зв'язності: а - Сильний зв'язний граф; б - односторонньо зв'язний граф; в - Cлабо зв'язний граф; г - незв'язних граф
Орграф називається односторонньо зв'язковим, або одностороннім, якщо для будь-яких двох різних його вершин х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} є слабкими компонентами, і у цього графа тільки дві компоненти.
З визначень відразу ж випливає, що односторонні компоненти графа можуть мати загальні вершини. Сильна компонента повинна міститися принаймні в одній односторонньої компоненті, а одностороння компонента міститься в деякій слабкою компоненті даного графа.
