无向图和有向图

1.无向图

两点之间的边没有方向。点（Vertex）简称V,边（Edge）简称E

2.有向图

 

两点之间的边是有方向的

有多少边以某点为出发点 则有多少的出度，同理有多少边以某点为终点则有多少入度，

度=出度+入度

3. 邻接矩阵

 

用G=（V,E）表示上图的无向图，V表示顶点集合V=v1,v2,v3,etc，E表示边的集合e1,e2,e3,etc

用aij表示vi和vj两个顶点之间的边的数量关系得到的矩阵A=A（G）即为图G的邻接矩阵。

对于上图可得邻接矩阵A:

\begin{bmatrix} 0 &1 & 0 &1 \\ 1& 0 & 1 &0 \\ 0 & 1& 0 &1 \\ 1&0 &1 &0 \end{bmatrix} 

4.关联矩阵

 

同样的用mij表示vi和边ej之间的关系（专门指有向图）顶点是边的出发点m取1，相反是终点取-1，无关则取0

对于上图可得关联矩阵M:

\begin{pmatrix} 1 & 0& 0 &-1 \\ -1 &-1 & 0 &0 \\ 0& 1&-1 &0 \\ 0& 0&1 & 1 \end{pmatrix}