NLP前置基礎（圖論）

無向圖

無向圖 G可以定義為一個二元組G=（N,E），其中，N是頂點的非空有限集合；E是邊的有限集合。
G=（N,E）
N={V1,V2,V3,V4,V5,V6}
E={(V1,V2),(V1,V3),(V1,V4),(V2,V5),(V3,V4),(V3,V5),(V3,V6),(V4,V6),(V5,V6)}

有向圖

有向圖 D可以定義為一個二元組D=（N,E），其中，N是頂點的非空有限集合，E是邊的有限集合。
D=(N,E)
N={V1,V2,V3,V4,V5,V6}
E={(V1,V2),(V1,V5),…,(V5,V3),(V5,V6)}

連通圖

連通圖是一個無向圖G=(N,E)或有向圖D=（N,E）,對於N中的任意兩個頂點，存在一個頂點的序列 P，（肉眼可見的連線），則P也被稱為圖G或D的一條路徑或者通路。

-迴路
開始與終結於同一頂點的通路稱為迴路（自迴路）（非頻繁的）；若圖中無任何迴路，則稱該圖為無迴路圖。

樹

-樹：一個無迴路的無向圖稱為森林；一個無迴路的連通無向圖稱為樹（自由樹）。
如果樹中有一個結點被特別地標記為根節點，那麼這棵樹稱為根樹。
-樹是包含n個節點的有窮集合S（n>0），且在S上定義了一個關係R，R滿足以下三個條件：
（1）有且僅有一個結點t₀∈S，該結點對於R來說沒有前驅，結點t₀稱作樹根；
（2）除了結點t₀以外，S中的每個結點對於R來說，都有且僅有一個直接前驅；
（3）除了結點以外的任何結點t∈S，都存在一個結點序列t₀，t₁，…，tk，使得t₀為樹的根，tk=t，有序對<ti-1，ti>∈R（1≤i≤k），則該結點序列稱為從根節點t₀到結點t的一條路徑。
-在根樹中，自上而下的路徑末端結點稱為樹的葉結點，介於根節點與葉結點之間的結點稱為中間結點（或稱內結點）。