一起學(xué)習(xí)圖論

?最近在學(xué)習(xí)圖論，所以打算寫一下圖論的淺顯概念。

一、起源

普瑞格爾河從古城哥尼斯堡市中心流過，河上筑有七座古橋,如圖1.1（a）。

1736年，一位數(shù)學(xué)者向數(shù)學(xué)家Euler提出這樣的問題：從家里出發(fā)，七座橋每橋恰通過一次，再回到家里，是否可能？后來Euler對問題進行抽象和論證，如圖1.1（b）,從而得到否定的答案，由此開創(chuàng)了圖論的元年。

二、基本概念

稱一個數(shù)學(xué)結(jié)構(gòu)G={V,E}，其中V是頂點集合，E是邊長的集合。若e屬于E,（u,v）屬于V×V，則簡寫為e=uv;我們稱u是有向邊的尾，v是有向邊的頭。

把頂點u與v這兩點用箭頭從u指向v的一條有向曲線連接起來,此曲線的長短與曲直不加考慮，我們稱這樣的圖為有向圖（圖2.1所示）。當(dāng)把圖2.1的箭頭都去掉的話，那么得到的是一個無向圖。

我們給出以下定義：

（1）邊的端點：e=wv時,稱頂u與v是邊e的端點。

（2）邊與頂相關(guān)聯(lián)：若邊e的端點是u與v,則稱e與u，v相關(guān)聯(lián)。

（3）鄰頂：同一條邊的兩個端點叫做鄰頂。

（4）鄰邊：與同一個頂相關(guān)聯(lián)的兩條邊叫做鄰邊。

（5）環(huán)：只與一個頂相關(guān)聯(lián)的邊叫做環(huán)。

（6）單圖：無環(huán)無重邊的圖.

三、一類圖

完全圖：任二頂皆相鄰的圖。

remark：完全圖具有最多的邊數(shù)；任意一對頂點間均有邊相連。