圖論基礎
1.基本概念
圖可以理解成一個二元組，是由點集V和邊集E組成的
G = (V, E), V表示點的集合，E表示邊的集合，
每條邊是一幅點對(v, w) v, w都是點集V中的點，(v, w∈V)
2.圖的分類
可以按照邊有無方向，可以分為有向圖和無向圖，
比如上圖1中，邊AB之間沒有畫出方向（即點之間是無序的），這就是無向圖，
無向圖：每條邊都是無向的圖為無向圖，
有向圖：每條邊都是有向的圖為有向圖，
3.圖的分類
可以按照邊的數量分為，簡單圖和多重圖
簡單圖：在無向圖中，任意2點間只有1條邊；在有向圖中，任意2點間不只有1條同向邊
多重圖：在無向圖中，任意2點間不止有1條邊；在有向圖中，任意2點間不止有1條同向邊
4.圖的度
在無向圖中，與這個結點相連的邊的個數，稱為結點的度，比如在圖1中，X的度數為4
在有向圖中，結點的度分為入度和出度，
結點的入度：以這個節點為終點的有向邊的個數
結點的出度：以這個節點為起點的有向邊的個數
比如在圖2中，A的入度為0，出度為2
性質：圖的總度數 = 遍數 * 2
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-xFm6LaDz-1619851736770)(https://codingtang.oss-cn-hangzhou.aliyuncs.com/2021050114335186.png)]
5．連通
無向圖中:從任意點，都存在到達其它點的路徑，稱為連通圖，
有向圖中:從任意點，都存在到達其它點的路徑，稱該有向圖是強連通的
6.子圖
對于圖G和圖G’,如果圖G’的邊集和點集都是圖c的邊集和點集的子集，那么圖G’是圖G的子圖
7．匯出子圖
對于圖G和圖c’,如果圖G’妳的點集都是圖c點集的子集，那么圖G’是圖6的匯出子圖，其邊集不一定是圖c邊集的子集，
8．補圖
對于圖c和圖G’，如果2個圖的點集相同，邊集沒有交集，并且邊集為完全圖的邊集，那么圖c和圖c’互為補集，
9．其它概念
權值:邊的“費用”，可以看成是邊的長度
回路:起點和終點相同的路徑，稱為“回路”，或者"環”完全圖:
無向圖中，如果任意兩點之間都存在一條邊，則是一個無向完全圖，無向完全圖有n*(n-1)/2條邊;
有向圖中，如果任意兩點之間都存在互通的兩條邊，則是一個有向完全圖，有向完全圖有n*(n-1)條邊，稠密圖:邊數接近于完全圖的圖
稀疏圖:邊數遠遠少于完全圖的圖
強連通分量:有向圖中任意兩點都連通的最大子圖，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/282682.html
標籤：其他