A-level 數學/MEI/D1/圖

離散數學中的圖與連續數學中的圖略有不同。在連續數學中，圖用於視覺化兩個變數之間的對映（例如 y=x²）。在離散數學中，圖描述了物件之間的關係，這些物件被稱為頂點或節點，這些物件透過邊連線。邊可以是無向的或有向的，如果它們是有向的，則使用箭頭來指示邊的遍歷方向。由頂點和邊連線而成的圖被稱為圖。

可以使用以下集合推導從兩個集合建立頂點對（如果您不熟悉集合推導，該表示式表示從兩個集合：X 和 Y 中，生成每對可能的排列）。 $X\times Y=\{(x,y)|x\in X,y\in Y\}$

例子

$X=\{London,Cambridge,Birmingham\}$
$X\times X=\{(London,London),(London,Cambridge),(London,Birmingham),$
$(Cambridge,London),(Cambridge,Cambridge),(Cambridge,Birmingham),$ $(Birmingham,London),(Birmingham,Cambridge),(Birmingham,Birmingham)\}$

術語表

基本定義

圖: 由物件組成的圖，其中一些物件透過邊連線。相互連線的物件稱為頂點或節點，連線節點的連結稱為邊。
頂點/節點的度數/階數: 連線到該頂點/節點的邊的數量。
迴路: 當一條邊的末端是下一條邊的起點並且沒有頂點重複時形成的閉合路徑。
有向邊: 與方向相關的邊，這用箭頭表示邊的遍歷方向。
自環: 兩端都具有相同頂點的邊。
有向圖: 有向圖，至少有一條邊與方向相關的圖。

以下定義按普遍性排序，通路是最通用的，而哈密頓迴路是最不通用的。

通路: 一系列邊，其中一條邊的末端是下一條邊的起點。如果最後一條邊連線到第一條邊，則通路是閉合的，如果它沒有連線，則通路是開放的。
軌跡: 沒有邊重複的通路。
路徑: 沒有頂點重複的軌跡。
迴路: 最後一條邊的末端連線到第一條邊的圖。
哈密頓迴路: 恰好訪問每個頂點一次的迴路。

圖的型別

連通圖: 每對頂點之間都存在路徑的圖。
簡單圖: 沒有自環且任意一對邊之間不超過一條邊的圖。
完全圖: 每對頂點之間都由一條邊連線的簡單圖。
平面圖: 可以不交叉任何一對邊的圖。
二分圖: 由兩組頂點組成的圖，每條邊連線一組中的一個頂點和另一組中的一個頂點。
有向圖: 包含有向邊的圖。
樹: 沒有迴路的簡單連通圖。

圖的例子

這些例子是OCR MEI 能力規範中列出的例子，因此，在參加考試之前充分理解它們是明智的。

哥尼斯堡七橋問題

據說，在柯尼斯堡不可能不重複走過任何一座橋的情況下走完七座橋。尤拉研究了這個問題，將其轉化為圖論，並證明了 *任何具有奇數個頂點的圖都不能被遍歷*。

這個問題被轉化為一個圖，將橋視為邊，將陸地視為節點。這種抽象掉無關細節的做法使尤拉能夠專注於問題的核心屬性，是建模任何問題的基本方面。

尤拉推斷，當透過一座橋（邊）進入一塊陸地（節點）時，會透過另一座橋離開該陸地，因此進入一個節點的次數與離開該節點的次數相同，因此穿過陸地的橋的數量必須是偶數（前提是該節點 *不是* 起點或終點，在這種情況下，進入的次數是奇數）。由此得出，每個陸地（除選擇作為起點和終點的陸地外）必須有偶數座橋（邊）。問題中的所有四個陸地都與奇數座橋相連，最多隻有 2 塊陸地可以作為步行路線的起點/終點，因此橋樑不可能在一次步行中只走一次。

更正式地說
尤拉推斷，當透過一條邊進入非終點（非起點/終點）節點時，會透過另一條邊離開該節點，因此進入該節點的次數

尤拉路徑是一種遍歷所有邊一次的路徑，起點和終點可以相同或不同。如果起點和終點相同，則該路徑被稱為歐拉回路。對於一個圖來說，要想有一個歐拉回路，必須有零個奇數度節點，而尤拉路徑可以有零個或兩個奇數度節點。任何可以透過一次不抬起筆從紙上描繪所有邊並且回到起點的圖被稱為 *尤拉圖* 或 *可遍歷圖*。

過河

立方體塔

有四個立方體，每個立方體都有四個不同的顏色在其面上。這個謎題的目標是將這些立方體堆疊在一起形成一個 4x1x1 的長方體，這樣長方體的每個面上都有四種不同的顏色。立方體的塗色如下：

立方體 1	立方體 2	立方體 3	立方體 4
藍色對面是綠色	B 對面 G	R 對面 B	Y 對面 R
紅色對面是紅色	G 對面 R	R 對面 Y	Y 對面 G
黃色對面是藍色	B 對面 Y	G 對面 Y	B 對面 G