Компонента зв’язності графа - це

Незв'язний граф з трьома компонентами зв'язності

Компонента зв'язності графа - деякий безліч вершин графа таке, що для будь-яких двох вершин з цієї множини існує шлях з однієї в іншу, і не існує шляху з вершини цієї множини в вершину не з цієї множини.

Для орієнтованих графів визначено поняття сильної компоненти зв'язності

Для пошуку компонент зв'язності можна використовувати пошук в ширину або пошук в глибину. При цьому витрачений час буде лінійним (щодо кількості вершин і ребер).

Для поліпшення цієї статті з математики бажано.

Дивитися що таке "Компонента зв'язності графа" в інших словниках:

Компонента сильної зв'язності графа - Орграф називається сильно зв'язковим (strongly connected), якщо будь-які дві його вершини сильно пов'язані. Дві пари вершин s і t будь-якого графа сильно пов'язані, якщо існує орієнтований шлях з s в t і орієнтований шлях з t в s. Сильно зв'язковими ... ... Вікіпедія

Компонента - Компонент (від лат. Componens, родовий відмінок componentis що становить) складова частина, елемент чогось. У різних галузях науки і техніки може мати додаткове, більш специфічне значення. В математиці склалося вживання в ... ... Вікіпедія

ГРАФА зв'язність - одна з топологічних характеристик графа. Граф зв. зв'язковим, якщо для будь-яких його вершин і н vсуществует ланцюг, що з'єднує ці вершини. Числом вершинної зв'язності графа G [позначення] зв. найменше число вершин, видалення до яких (разом з ... ... Математична енциклопедія

ГРАФА автоморфізм - изоморфное відображення графа на себе (див. Графів ізоморфізм). Безліч всіх автоморфізмів даного графа утворює групу щодо операції композиції автоморфізмів. Автоморфізм графа Gпорождают групу підстановок вершин Г (G), наз. групою ... ... Математична енциклопедія

Компонента сильної зв'язності графа - Орграф називається сильно зв'язковим (англ. Strongly connected), якщо будь-які дві його вершини сильно пов'язані. Дві вершини s і t будь-якого графа сильно пов'язані, якщо існує орієнтований шлях з s в t і орієнтований шлях з t в s. ... ... Вікіпедія

Компонент - Компонента складова частина чогось цілого. У різних галузях науки і техніки може мати додаткове, більш специфічне значення. В математиці Компонента зв'язності Компонента зв'язності графа Компонента вектора або тензора, см. ... ... Вікіпедія

Словник термінів теорії графів - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И К Л М Н О П Р С ... Вікіпедія

Глосарій теорії графів - Ця сторінка глосарій. Див. Також основну статтю: Теорія графів Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці) ... Вікіпедія