Деревья. Связность. Дерево и его виды
Связность. Дерево и его виды Множество вершин графа таких, что любые две из него связаны, а связи с вершинами не из этого множества нет, называется компонентой связности графа. Рис. 1 v1 v2 v3 v4 v5 v6 v7 v8 Рис. 2 v1 v2 v3 v4 v5 v6 v7 Неорграф на рис. 1 имеет 4 компоненты связности: {v1}, {v2,v3,v4}, {v5,v6,v7}, {v8}. Орграф на рис. 2 имеет 2 компоненты связности: {v1, v2, v3}, {v4, v5, v6, v7}. Граф, содержащий одну компоненту связности, называется связным. Например, все компьютеры, включённые в Интернет, образуют связный граф. Два конкретных компьютера могут быть не соединёнными напрямую, но от каждого информацию можно передать на любой другой. Связность означает наличие хотя бы одного пути - последовательности смежных неповторяющихся рёбер (дуг) между любой парой вершин графа (графы на рис. 1, 2 несвязные).