Граф называется связным, если множество его вершин нельзя разбить на два или более подмножеств так, чтобы ни одна вершина одного подмножества не отображалась в вершину другого. В противном случае граф называется несвязным. Число подмножеств, не связанных отображениями, на которое разбивается множество всех вершин графа, называется числом компонент связности для несвязного графа.
Существует другое определение связности графа. Граф называется связным, если две любые его вершины можно соединить цепью. Граф (рис. 3.1.3) является несвязным с двумя компонентами связности.
Рис. 3.1.3
Ребро графа называется перешейком, или связующей линией, если его удаление приводит к тому, что граф становится несвязным. На рис. 3.1.4 изображены три связных неориентированных графа, причем граф 1 не имеет ни одного перешейка, 2 содержит один перешеек (отмечен жирной линией), граф 3 целиком состоит из одних перешейков. Такой граф (3) называется деревом.
Рис. 3.1.4
