圖論一

起源于哥尼斯堡七橋問題…… 沒有重邊的就是簡單圖；兩點間是鄰接的，點和邊是關聯的。 完全圖(Kn)，n是圖階數(就是點數)，任何兩點間均有邊(直達路徑)。

圖G = {v,e}，頂點集和邊集。 圖的度序列(d1,d2……dn)，度數從大到小排列，完全圖的度全是n-1。 環的度是2。 一般圖:允許有重邊和環，所有頂點的度之和是偶數，即d1+d2+……+dn = 2e(e是邊數)，想想普通邊把兩個點的度增加1，而環把一個點的度增加2；奇點的個數是偶數個，是以一個圖裡不可能隻有一個奇點。 同構：g1 = {v1,e1},g2= {v2,g2}，若在v1和v2之間存在一個雙射西塔(滿單射，就是一一映射)，滿足“x1，y1在g1中是鄰接的”的充要條件(說明邊數頂點數要相同，即|e1|=|e2|，實際上邊數相同的話頂點數肯定相同)是x2，y2在中是鄰接的，那麼兩圖同構，g1（一個等号，上面）g2。

結論：同構的話點數相同、邊數相同，而且度序列相同。 度序列相同就同構嗎？不是的，看下圖(直覺上一個圖裡有什麼第二個圖裡就有什麼，不過有些可能不一緻，比如平面性，在K4圖裡一個平面圖另一個是可平面圖)

m條相連邊，叫長度是m的途徑，若是不存在重複遍則就是迹，若是沒有重複點就是鍊，都有開閉之分。閉合鍊叫圈。 途徑分為若幹圈和一個鍊；鍊一定是迹(點不重肯定邊不重)。