Posted on 2007-06-03 20:06
ZelluX 阅读(704)
评论(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 任意两点间都有边