【资料结构】图的基本定义

一个图形具有两个集合的基本组成:G(V,E)

• V:表示顶点的集合

    V(G1)={1,2,3,4}
  

• E:表示边的集合

    E(G1)={(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(2,3)}
  

无向图与有向图

• 无向图:图的边不具有方向性

    (V0,V1)=(V1,V0)
  

• 有向图:图的边具有方向性

    <V0,V1>!=<V1,V0>
  

  <u,v>表示u-->v

        u是边的尾巴
        v是边的头
  

图的限制

• 自我边:从同一个顶点出发，连接到自己
• 重复边:两个顶点重复连接

完全图

一个图形有最大的边数量

设顶点数为n
    无向图:n(n-1)
    有向图:n(n-1)/2

邻近与附接

子图

属於图的子集合为子图

路径相关

路径:从顶点到顶点所经过的边

长度:路径上的边数目

除了第一个点和最後一个点，其余经过顶点不重复为简单路径，当第一个点和最後一个点相同时可称为回圈。

强连结组件

强连结:在有向图中，点u连向v，点v连向u

强连结组:具有强连结的最大子图

分支度

该顶点附接的边数量
有向图:

• in-degree:以顶点作为箭头的数量
• out-degree:以顶点作为箭尾的数量