咱們開始先看一個著名的格斯堡七橋問題：

能否從任一陸地出發通過每座橋恰好一次而回到出發點？

你要是自己做過，就會顯而易見的發現這道題是沒有答案的（遵守規則以及圖形規定的情況下）

歐拉就這個問題說過：如果每塊陸地所連接的橋都是偶數座，則從任一陸地出發，必能通過每座橋恰好一次而回到出發地。

經過此次引導我們回到圖論的基本概念

首先先看圖論的定義：

一個有序二元組 (V, E ) 稱為一個圖, 記為G = (V, E )

其中：

① V或V(G)稱為G的頂點集, 其元素稱為頂點或結點, 簡稱點;

② E或E(G)稱為G的邊集, 其元素稱為邊, 它聯結V 中的兩個點, 如果這兩個點是無序的, 則稱該邊為無向邊, 否則, 稱為有向邊.

tip:可以用|V|或者|E|表示圖G的定點數和邊數

且如果V = {v1, v2, … , vn}是有限非空點集, 則稱G為有限圖或n階圖.

如果E的每一條邊都是無向邊, 則稱G為無向圖

如果E的每一條邊都是有向邊, 則稱G為有向圖;

否則, 稱G為混合圖.

可以參考一下圖形實例

?如圖，左圖為無向圖，右圖為有向圖

---

?記E = {e1, e2, … , em}(e(k)?= v(i)v(j)?).

但在之后學習的過程中，你最后可能會找到一些不一樣的圖，但最終的話圖解是相同的

例如以下的圖：

?

?

?為了方便處理，我沒有在上面進行標號端點，但實際上兩個圖雖然看上去不一樣，但實際圖解是相同的

?這就可以衍生到之前說過的

對于一個圖G = (V, E ), 人們常用圖形來表示它, 稱其為圖解.

凡是有向邊, 在圖解上都用箭頭標明其方向.

一個圖會有許多外形不同的圖解，它們之間稱做同構，如圖G同構圖H記作G~=H

---

那么我們接下來：(都是一些最基本的概念理論，可能有一點枯燥)

稱點v(i), v(j)為邊v(i)v(j)的端點.

在有向圖中:

稱點v(i), v(j)分別為邊v(i)v(j)的始點和終點.

稱邊v(i)v(j)為v(i)的出邊, v(j)的入邊.

稱v(j)是v(j)的后繼或子頂點，稱v(i)是v(j)的前驅或父頂點。

有邊聯結的兩個點稱為相鄰頂點,

有一個公共端點的邊稱為相鄰邊.

邊和它的端點稱為互相關聯.

有向圖中的關聯又分出關聯和入關聯。

常用d (v)表示圖G中與頂點v關聯的邊的數目,

d (v)稱為頂點v的度數.

與頂點v出關聯的邊的數目稱為出度，記作d +(v),

與頂點v入關聯的邊的數目稱為入度，記作d -(v)。

用N (v)表示圖G中所有與頂點v相鄰的頂點的集合.

兩個端點重合的邊稱為環。

無向圖中有相同端點的邊稱為平行邊,

有向圖中有相同的頭與尾的邊稱為平行邊。

沒有關聯邊的頂點稱為孤立點。

恰有一條關聯邊的頂點稱為懸點，

與懸點關聯的的邊稱為懸邊。

tip:在計算與頂點關聯的邊時，環算作兩條邊

有向圖G略去邊的方向，得到一個無向圖，此時這份新的圖稱為圖G的基礎圖。

有n個頂點m條邊的圖稱為(n,m)圖。

（n,0）圖叫零圖。（1,0）圖叫平凡圖

沒有環與平行邊的圖稱為簡單圖.

任意兩頂點都相臨的簡單圖稱為完全圖.

有n個頂點的完全圖記為K n

tip:若頂點V(G)能分解成兩個不相交的子集V(1)和V(2),即V(2)并V(2)為V，V(1)交V(2)=空

且V(i)自身的頂點不相鄰，則稱G為偶圖（兩部圖）。

而不在同一頂點子集的任意兩個頂點都相鄰的簡單偶圖就被稱為完全偶圖

---

那么接下來大家可以靠圖論的知識解決狼羊渡河問題（雖說心算也可以）：

但這可以說是入門級別的圖論應用之一了：

一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河東，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨處，給出渡河方法。

用四維0-1向量表示（人，狼，羊，菜）的在西岸狀態，（在西岸則分量取1，否則取0.）

共=16種狀態，

由題設，狀態（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，

從而對應狀態（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許的，

以十個向量作為頂點，將可能互相轉移的狀態連線，則得10個頂點的偶圖。

那么此題就不過多贅述了；

---

若將圖G的每一條邊e都對應一個實數F (e), 則稱F (e)為該邊的權, 并稱圖G為賦權圖(網絡), 記為

G= (V, E , F ).

設G = (V, E )是一個圖, v0, v1, … , vk∈V, 且“1≤i≤k, vi-1 vi∈E, 則稱v0 v1 … vk是G的一條通路.稱為v0- vk通路.稱其長為k，起點與終點重合的通路稱為閉通路，不重合的稱為開通路。

如果通路中沒有相同的邊, 則稱此通路為道路.(跡)

如果通路中沒有相同的頂點, 則稱此通路為路徑, 簡稱路.

始點和終點相同的路稱為圈或回路.

有向圖中邊的方向與通路，道路，路的方向一致。

頂點u與v稱為連通的，如果存在u-v通路，任二頂點都連通的圖稱為連通圖，否則，稱為不連圖。

極大連通子圖稱為連通支。

連通而無圈的圖稱為樹, 常用T表示樹.

樹中最長路的長稱為樹的高

樹的度為1的頂點稱為樹葉。

其余的頂點稱為分枝點。樹的邊稱為樹枝。

設G是有向圖，如果G的基礎圖是樹，則稱G是有向樹，也簡稱樹：

設T是有向樹，若存在頂點v0可達其余的每一頂點，則稱T為外向樹， v0為始根。若存在頂點v0，其余的每一頂點都可達v0，則稱T為內向樹， v0，為終根。外向樹與內向樹統稱為有根樹。

設G是有向圖，如果G的基礎圖是樹，則稱G是有向樹，也簡稱樹。

設T是有向樹，若存在頂點v0可達其余的每一頂點，則稱T為外向樹， v0為始根。若存在頂點v0，其余的每一頂點都可達v0，則稱T為內向樹， v0為終根。外向樹與內向樹統稱為有根樹。

---

圖的矩陣表示 ：⑴ 鄰接矩陣 )n×n

以下為例題：

答案：

?⑵ 權矩陣A = (aij ) n×n

例題如下：

答案：

?⑶ 關聯矩陣A = (aij )n×m? ：

有向圖：

?無向圖：

?今天的筆記就到這里了，下期再見，拜拜

?

?

?

總結

以上是生活随笔為你收集整理的图论及其应用（基础知识）（1）（数学建模基础速成）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。