圖論

出自 MBA智库百科(https://wiki.mbalib.com/)

圖論(Graph Theory)

　　圖論是指研究圖和網路的數學分支，常被認為包含於組合數學中，但這一分支已經發展得足夠龐大和有特點，並有自身領域所研究的問題，因此被視為一個獨立的主題。

　　圖G=（V,E）是一個二元組（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。為了避免符號上的混淆，我們總是預設V∩B=Ø。集合V中的元素稱為圖G的定點（或節點、點），而集合E的元素稱為邊（或線）。通常，描繪一個圖的方法是把定點畫成一個小圓圈，如果相應的頂點之間有一條邊，就用一條線連接這兩個小圓圈，如何繪製這些小圓圈和連線時無關緊要的，重要的是要正確體現哪些頂點對之間有邊，哪些頂點對之間沒有邊。

　　由於生產管理、軍事、交通運輸、電腦和通訊網路等方面的大量問題的出現，大大促進了圖論的應用。特別是電子電腦的大量應用，更使大規模圖論問題的求解成為可能。實際問題如電網路、交通網路、電路設計、數據結構以及社會科學中的問題所涉及的圖形都是很複雜的，需要電腦的幫助才有可能進行分析和解決。

　　目前圖論在電信網路、開關理論、編碼理論、可靠性理論、電腦程式設計、故障診斷、人工智慧、印刷電路板的設計、圖案識別、地圖著色等計算科學的學科領域都有十分廣泛的應用。