圖的基本概念

圖是由稱為節點或頂點的點集以及由稱為邊的線連線的點集組成。圖的研究，或圖論，是數學、工程和計算機科學領域許多學科的重要組成部分。

圖論

定義 − 圖（表示為 G = (V, E)）由非空頂點集或節點 V 和邊集 E 組成。頂點a表示邊的端點。一條邊連線兩個頂點a, b，並由它連線的頂點集表示。

示例 − 讓我們考慮一個圖 G = (V, E)，其中 V = {a, b, c, d}，E = {{a, b}, {a, c}, {b, c}, {c, d}}

頂點的度 − 圖 G 的頂點 V 的度（用 deg (V) 表示）是與頂點 V 關聯的邊的數量。

偶數頂點和奇數頂點 − 如果頂點的度是偶數，則該頂點稱為偶數頂點；如果頂點的度是奇數，則該頂點稱為奇數頂點。

圖的度 − 圖的度是該圖中最大的頂點度。對於上面的圖，圖的度為 3。

握手引理 − 在一個圖中，所有頂點的度之和等於邊數的兩倍。例如，在上述情況下，所有頂點的度之和為 8，總邊數為 4。

Mahesh Parahar

更新於：2019年8月23日

4K+ 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始