---
title: 圖論概述
tags: 演算法
description: 簡述演算法和資料結構中的圖論
---
# 圖論概述

如果說到圖，各位腦海中浮現的會是什麼畫面呢？

||~~筆者我腦中的是色圖~~||

在數學上，「圖Graph」，有著獨特的意義，並非是泛指我們日常生活中看到的圖畫那種圖，而是如同下圖的結構。


## 圖 Graph

圖，由兩種構造組成，分別是
- 點Vertex，時常簡寫為V
- 邊Edge，時常簡寫為E

以$G = (V, E)$表示之
`G`表示圖本身
`V`表示點集，也就是點的集合
`E`表示邊集，也就是邊的集合

並且會以`e = {x, y} ∈ E`表示x和y之間的連通關係
而`{}`是不分方向性的，意味著`{x, y}`與`{y, x}`是等價的。

### 有向圖 Directed Graph

前面提到，使用{x, y}表示的圖並沒以方向性

不過，有時候你會看到這樣的圖

這種圖被稱為有向圖，正如其名，方向性是存在的
此時`e = (x, y) ∈ E`，意味著`x->y`

:::info
有沒有發現，Tree也是一種有向圖喔
:::

### 賦權圖

有時候，點與點之間會有所謂的權重，也就是每一條邊都有權重問題，此時除了{x,y}以外，會額外再多一個`w`去表示兩點之間的權重，記為`{x, y, w}`

權重有許多涵義，常見的用途是用以紀錄兩點間的距離，或者所需要花費的時間及成本。

### 環 Cyclic

當某張圖在巡迴的時候，我從某個點出發，能夠有某種方式再回到自己出發的位置，則這樣的圖被稱為==帶環==

### 有向無環圖 Directed Acyclic Graph

簡稱為DAG，在討論拓樸排序、工作流等議題時會出現。
正如其名，意思是有向圖，且不帶環。

## reference

> [link text](https:// "title")
> [name=Miyago]