圖論中的基本概念有：1 完全圖：若一個圖的每一對不同頂點恰有一條邊相連，則稱為完全圖。2 團：對於給定圖G=(V,E)。V是圖G的頂點集，E是圖G的邊集。圖G的團就是一個兩兩之間有邊的頂點集合。簡單地說，團是G的一個完全子圖。3 極大團：如果一個團不被其他任一團所包含，即它不是其他任一團的真子集，則稱該團為圖G的極大團。4 最大團：頂點最多的極大團，稱之為圖G的最大團。5 獨立集：獨立集是指圖G=(V,E)中兩兩互不相鄰的頂點構成的集合。6 極大獨立集：如果K是G的獨立集，且不是任何其他獨立集的真子集，就為極大獨立集。7 最大獨立集：極大獨立集中元素最多的集合為最大獨立集。8 補圖：圖G的補圖，通俗的來講就是完全圖Kn去除G的邊集後得到的圖Kn-G。9 最大獨立集中頂點數量= 補圖的最大團中頂點數量。擴充套件資料：定義：圖G=（V,E）是一個二元組（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。為了避免符號上的混淆，我們總是預設V∩B=Ø。集合V中的元素稱為圖G的定點（或節點、點），而集合E的元素稱為邊（或線）。通常，描繪一個圖的方法是把定點畫成一個小圓圈，如果相應的頂點之間有一條邊，就用一條線連線這兩個小圓圈，如何繪製這些小圓圈和連線時無關緊要的，重要的是要正確體現哪些頂點對之間有邊，哪些頂點對之間沒有邊。引理1有向圖G無迴路當且僅當對G進行深度優先搜尋沒有得到反向邊。證明：→：假設有一條反向邊(u,v)，那麼在深度優先森林中結點v必為結點u的祖先，因此G中從v到u必存在一通路，這一通路和邊(u,v)構成一個迴路。←：假設G中包含一回路C，我們證明對G的深度優先搜尋將產生一條反向邊。設v是迴路C中第一個被發現的結點且邊(u,v)是C中的優先邊，在時刻d[v]從v到u存在一條由白色結點組成的通路，根據白色路徑定理可知在深度優先森林中結點u必是結點v的後裔，因而(u,v)是一條反向邊。（證畢）
圖論中的基本概念有：1 完全圖：若一個圖的每一對不同頂點恰有一條邊相連，則稱為完全圖。2 團：對於給定圖G=(V,E)。V是圖G的頂點集，E是圖G的邊集。圖G的團就是一個兩兩之間有邊的頂點集合。簡單地說，團是G的一個完全子圖。3 極大團：如果一個團不被其他任一團所包含，即它不是其他任一團的真子集，則稱該團為圖G的極大團。4 最大團：頂點最多的極大團，稱之為圖G的最大團。5 獨立集：獨立集是指圖G=(V,E)中兩兩互不相鄰的頂點構成的集合。6 極大獨立集：如果K是G的獨立集，且不是任何其他獨立集的真子集，就為極大獨立集。7 最大獨立集：極大獨立集中元素最多的集合為最大獨立集。8 補圖：圖G的補圖，通俗的來講就是完全圖Kn去除G的邊集後得到的圖Kn-G。9 最大獨立集中頂點數量= 補圖的最大團中頂點數量。擴充套件資料：定義：圖G=（V,E）是一個二元組（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。為了避免符號上的混淆，我們總是預設V∩B=Ø。集合V中的元素稱為圖G的定點（或節點、點），而集合E的元素稱為邊（或線）。通常，描繪一個圖的方法是把定點畫成一個小圓圈，如果相應的頂點之間有一條邊，就用一條線連線這兩個小圓圈，如何繪製這些小圓圈和連線時無關緊要的，重要的是要正確體現哪些頂點對之間有邊，哪些頂點對之間沒有邊。引理1有向圖G無迴路當且僅當對G進行深度優先搜尋沒有得到反向邊。證明：→：假設有一條反向邊(u,v)，那麼在深度優先森林中結點v必為結點u的祖先，因此G中從v到u必存在一通路，這一通路和邊(u,v)構成一個迴路。←：假設G中包含一回路C，我們證明對G的深度優先搜尋將產生一條反向邊。設v是迴路C中第一個被發現的結點且邊(u,v)是C中的優先邊，在時刻d[v]從v到u存在一條由白色結點組成的通路，根據白色路徑定理可知在深度優先森林中結點u必是結點v的後裔，因而(u,v)是一條反向邊。（證畢）