最大連通子圖

也就是把圖的所有結點用最少的邊將其連線起來的子圖，所以極大連通子圖不唯一，也就是因為這個原因可以說最大連通子圖是一個累贅概念，因為任何一個極大連通子圖，其實都可以叫做最大連通子圖，但是一般都不這么叫。