Posted on 2007-06-03 20:06
ZelluX 閱讀(719)
評論(0) 編輯 收藏 所屬分類:
Algorithm
USACO上的簡單介紹，都快忘了各個術語的中文名了
graph
vertex 頂點 (pl. vertexes / vertices)
edge
edge-weighted 帶權圖（貌似中文是這么叫的吧）
weight
self-loop 自環
simple graph 簡單圖，不存在自環或兩條（及以上）連接相同兩點的邊。multigraph 與之相對
degree
adjacent (to)
sparse graph 稀疏圖，邊數少于最大值（n*(n-1)/2）的圖。與之相對的是dense graph。
(un)directed graph (有)無向圖
out-degree in-degree 有向圖頂點的出度/入度
path
cycle 回路
圖的表示：
edge list
adjecency matrix
adjacency list
implict
連通性：
connected
component 連通分量
strongly connected component 強連通分量
subgraph 子圖. The subgraph of G induced by V' is the graph (V', E')
bipartite 二分圖
complete 任意兩點間都有邊