Компонента связности графа

Компонента связности графа
Несвязный граф с тремя компонентами связности

Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

Для ориентированных графов определено понятие сильной компоненты связности

Алгоритм

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

См. также

Ссылки

Видеозапись лекции посвященной связности графов



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Компонента связности графа" в других словарях:

  • Компонента сильной связности графа — Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две пары вершин s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными… …   Википедия

  • Компонента — Компонент (от лат. componens, родительный падеж componentis составляющий) составная часть, элемент чего либо. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. В математике сложилось употребление в… …   Википедия

  • ГРАФА СВЯЗНОСТЬ — одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение ] наз. наименьшее число вершин, удаление к рых (вместе с… …   Математическая энциклопедия

  • ГРАФА АВТОМОРФИЗМ — изоморфное отображение графа на себя (см. Графов изоморфизм). Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа Gпорождают группу подстановок вершин Г(G), наз. группой… …   Математическая энциклопедия

  • Компонента сильной связности в орграфе — Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s.… …   Википедия

  • Связность графа — Связный граф граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует по крайней мере один путь. Содержание 1 Примеры применения 2 Связность для орграфов …   Википедия

  • Компонент — Компонента  составная часть чего либо целого. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. В математике Компонента связности Компонента связности графа Компонента вектора или тензора, см.… …   Википедия

  • КС — Компонента связности графа Конституционный суд Контактная сеть Counter Strike Кубок Стэнли Корреспондентский счёт (к/с) Качугин, Солодовников (по другим данным Керосиновая смесь) Координационный совет Кран Самоходный (см. также Подъёмный кран#По… …   Википедия

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

  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»