Task2-1 圖的基本表示

自帶了關聯(lián)結構

圖嵌入 用d維向量表示圖的結點及關聯(lián)信息

圖的本體設計 ontology

圖的種類

• Undirected
• Dorected
• heterogeneous(異質(zhì)圖)
• G = （V,E,R,T） 節(jié)點種類不止一種
• Biparttite Graph（二分圖）
• 用 u和v表示兩類節(jié)點
• 二分圖的展開

節(jié)點連接數(shù)

節(jié)點連接數(shù)很多，可以反應節(jié)點的重要度

圖的基本表示-鄰接矩陣

！無向圖鄰接矩陣為對稱陣，有向圖不是

• 節(jié)點度的計算

！存在自己到自己的連接，對角線元素為1

！絕大多數(shù)矩陣時稀疏的 sparse,用鄰接矩陣占用內(nèi)存

圖的基本表示-連接列表和鄰接列表

• 連接列表

• 鄰接列表：記錄每個元素及指出的元素

• 例子

• 帶權重和不帶權重的圖

• 自己指向自己連接

圖的連通性

Connected graph

!disconneted圖的鄰接矩陣呈現(xiàn)分塊對角形式，若幾個connected components中有節(jié)點連接起來，會打破分塊對角形式

• 有向圖中，若任意兩節(jié)點可相互觸達，稱為強連通圖，若忽略方向后連通，稱為weakly connected

• 強連通域 SCCs
• SCC的分解