基本概念

1. 图论中的图是由若干个给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
2. 一个图可以用数学语言描述为。V(vertex)指的是图的顶点集，E(edge)指的是图的边集。
3. 度：设是边的端点，则称与相关联，与顶点关联的边数称为该顶点的度，记为。度为奇数的顶点称为奇顶点，度为偶数的顶点称为偶顶点。所有顶点的度数之和是边数的2倍，由此可知奇顶点的总数是偶数。
4. 道路：设，与和关联，则称是图的一条道路。是起点，是终点，k为路长。
5. 迹：各边相异的道路称为迹。
6. 轨道：各顶点相异的道路称为轨道，记为，是起点，是终点，k为路长。
7. 回路：起点与终点重合的道路称为回路。
8. 圈：起点与终点重合的轨道称为回路。
9. 连通图：图中任两顶点之间都存在道路的图称为连通图。

10. 距离：顶点，的距离是顶点,分别为起点和终点的最短轨道之长。

    图的分类

    

    图与网络的数据结构

    假设是一个简单无向图，顶点集合，边集，记。

    邻接矩阵表示法

11. 邻接矩阵记为，当为赋权图时，有

1. 当为非赋权图时，有

1. 当图的边数远小于顶点数时，邻接矩阵表示法表示会造成很大的空间浪费。

   稀疏矩阵表示法

2. 系数矩阵是指矩阵中零元素很多，非零元素很少的矩阵。稀疏矩阵存放非零元素的行标、列表、值。

3. Matlab中，有向图的邻接矩阵转稀疏矩阵直接使用sparse命令，反过来用full命令 ```matlab

   a=[1 0 0;0 5 0;3 0 0]

a =

 1     0     0
 0     5     0
 3     0     0

b=sparse(a)

b =

(1,1) 1 (3,1) 3 (2,2) 5

full(b)

ans =

 1     0     0
 0     5     0
 3     0     0

3. 对于无向图，邻接矩阵是对称阵，只需要使用下三角元素。
```matlab
>> a=[1 0 3 ;0 0 1;3 1 0]
a =
     1     0     3
     0     0     1
     3     1     0
>> tril(a)
ans =
     1     0     0
     0     0     0
     3     1     0