Граф называется связным, если от любой вершины можно добраться по рёбрам до любой другой. Иначе говоря, связный граф состоит из одной части. Если частей несколько, то граф называется несвязным, а каждая часть называется компонентой связности.