---
# System prepended metadata

title: 基礎圖論
tags: [MDCPP講義]

---

# 基礎圖論
###### tags: `MDCPP講義`

## 1. 圖論簡介

圖論是由若干的頂點及連接兩個頂點所連成的邊產生的圖形，通常用來表達點之間的某種關係。
在資訊領域的講法上，一張圖(graph)包括了頂點(vertex)、邊(edge)。
這裡有幾張圖片，分別都是一張圖。
我們在表示邊的方法，通常會寫成 $e=(u, v), u, v \in V$。
![](https://i.imgur.com/wxYlOhG.png)
來源: [Wikipedia](https://zh.wikipedia.org/wiki/%E5%9B%BE%E8%AE%BA)
![](https://i.imgur.com/yfHXrCU.png)
來源: [IT幫幫忙](https://ithelp.ithome.com.tw/articles/10264128)

## 2. 圖的分類

- 無向圖
    有向圖代表在每個邊中，其方向是雙向的，你能從$u$走到$v$，也能從$v$走到$u$，即$(u, v)=(v, u)$。
- 有向圖
    有向圖代表在每個邊中，其方向是單向的，你能從$u$走到$v$，但不能從$v$走到$u$，即$(u, v)\neq(v, u)$
    
## 3. 常見術語

- 簡單圖
    圖中不存在自環