Zusammenhängende Graphen, Komponenten

Man spricht von einem zusammenhängenden Graph G, wenn zu je zwei verschiedenen Knoten v,w in G ein Weg existiert, der v mit w verbindet. Ist G nicht zusammenhängend, dann zerfällt G in Komponenten, d.h. in zusammenhängende induzierte Untergraphen mit maximaler Knotenzahl.