生成子圖的意思是,如果一個圖G的子圖G1包含了G的所有結點,則稱該子圖為G的生成子圖;子圖就是從原圖中删去一些點或删去一些線或既删去一些點又删去一些線,剩下的部分,剩下的部分仍然是一個圖;生成子圖就是一種隻允許删去線,不允許删去點的子圖。