В чем разница между связной компонентой и сильной связностью в теории графов?

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

Связная компонента — это максимально связный подграф неориентированного графа. en.wikipedia.org Каждая вершина принадлежит ровно одному связному компоненту, как и каждое ребро. en.wikipedia.org Граф является связным тогда и только тогда, когда он имеет ровно один связный компонент. en.wikipedia.org

Сильная связность — понятие, которое используется для ориентированных графов. en.wikipedia.org neerc.ifmo.ru Ориентированный граф называется сильно связным, если между каждой парой вершин графа существует путь в каждом направлении. en.wikipedia.org То есть существует путь от первой вершины в паре ко второй, и другой путь от второй вершины к первой. en.wikipedia.org

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

Пользователь

Время добавления