圖 (圖論)

圖（粵拼：tou4，英文：graph）係圖論嘅基本研究對象；可以用嚟代表物件同物件之間嘅網絡或者關係。圖論所講並唔係幾何講嘅圖，而係一種抽象概念；呢種圖由一啲頂點（又叫結點、節點；vertices）同連結呢啲點嘅邊（edges）組成，畫出嚟嘅話後者可以係直線或者曲線，點同邊嘅位置亦可以變，只要唔影響邊嘅關係，冇分別。至於 ｢圖｣ 呢個名，係喺1878年首次提出嘅。

圖論嘅圖可以分有向圖（directed graph）同無向圖（undirected graph）兩種，分別係啲邊有冇方向之分：

• 無向圖：所有邊都冇方向，即係如果 A 同 B 之間有邊，咁 A→B 同 B→A 完全一樣。例如社交網絡，如果兩個人係朋友，關係通常係雙向嘅，即係 A 係 B 嘅朋友，B 亦都係 A 嘅朋友。數學上，一個 N 個節點嘅無向圖最多有 N(N-1)/2 條邊。無向圖可以用鄰接矩陣表示。
• 有向圖：邊有方向之分，即係 A→B 同 B→A 係兩條唔同嘅邊。例如 Twitter 追蹤網絡，A 追蹤 B，B 未必會追蹤 A，呢種單向關係就係典型嘅有向圖。數學上，一個 N 個節點嘅有向圖最多有 N(N-1) 條邊。

書目

• Centre for Education in Mathematics and Computing (February 8, 2017). "Graph Theory I" (PDF). Intermediate Math Circles (加拿大英文). 滑鐵盧大學. 喺2025年4月17號搵到.
• Centre for Education in Mathematics and Computing (February 15, 2017). "Graph Theory II" (PDF). Intermediate Math Circles (加拿大英文). 滑鐵盧大學. 喺2025年4月17號搵到.