Чтобы определить, существует ли связь между двумя вершинами, можно использовать понятие связности в теории графов: 3

• Граф называется связным, если в нём для любых двух вершин имеется маршрут, соединяющий эти вершины. 1

• Две вершины являются связанными, если они лежат в одной компоненте связности. 4 Изначально все вершины находятся в разных компонентах связности. 4 При добавлении ребра объединяются множества, в которых находятся его концы, если те различны. 4

Если хотя бы две вершины не соединены, граф называется несвязным или разомкнутым. 2