圖論法

圖論法是以圖作為研究對象的方法稱為圖論法。圖可以表示為由某些點及連線這些點的連線組成的圖形,也可抽象地定義為G=(V,E,Φ),其中V,E分別是圖的頂點和邊集合,Φ表示V,E間的某種函式關係。這樣,凡和二元關係有關的系統都可用圖來描述,從而用圖論法進行研究。在用圖論法研究問題時我們只注意兩頂點是否被一連線所連,而頂點的位置和連線的方式則無關緊要。歐拉在1736年解決了著名的哥尼斯堡七橋問題,從而成為圖論方法的創始人。1947年克希霍夫發展了樹的理論。

1857年凱萊為了計數有機化學中的同分異構體而提出了樹的計數方法。哈密頓1859年提出了圖論中的難題哈密頓(Hamilton)一圈問題。圖論中的著名難題之一四色猜想已於1976年由美國的阿普爾等人用電子計算機證明。圖論法不但是運籌學,電網路理論,計算機科學,經濟學不可缺少的數學工具,而且在開關理論,編碼理論,有機化學,理論物理,統計學,社會心理學等方面都有廣泛的套用。近幾十年來圖論法有了進一步的發展。心理學家用一張平面圖來代表一個人的生活空間。物理學家用圖論法來研究物理粒子的碰撞。線性規劃與運籌學的各個領域裡也以研究網路上流的形式利用了圖論法。仍存在大量難題期望能用圖論法來解決。

相關詞條

熱門詞條

聯絡我們