图的概念

概念
图是由顶点V的集合和边E的集合组成的二元组记G=（V，E）如下图是一无向图(顶点的前后顺序不限）

file:///C:/Users/20901/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpg

                 图1

V={V1,V2,V3,V4,V5}

E={(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)}

下图是一有向图（顶点分先后顺序）

file:///C:/Users/20901/AppData/Local/Temp/msohtmlclip1/01/clip_image003.gif

V={V1,V2,V3,V4}

E={<V1,V2>,<V2,V4>,<V1,V3>,<V3,V4>,<V4,V1>}

完全图（每一对不同的顶点都有一条边相连,n个顶点的完全图共有n（n-1）/2条边）
顶点的度：与顶点关联的边的数目，有向图中等于该顶点的入度与出度之和。
入度——以该顶点为终点的边的数目和
出度——以该顶点为起点的边的数目和

度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。
[定理1] 图G中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。
[定理2] 任意一个图一定有偶数个奇点。
6.2图的存储

1.邻接矩阵

       1(或权值)   表示顶点i和顶点j有边(i和j的路程)

A(i,j)={

       0 表示顶点i和顶点j无边

  如图1的矩阵表示为

file:///C:/Users/20901/AppData/Local/Temp/msohtmlclip1/01/clip_image004.gif

2.邻接表

  数组方法：

顶点     相邻顶点       邻接顶点数

v       d[i,j]            c

1		2	4	5			3
2		1	3	5			3
3		2	4				2
4		1	3	5			3
5		1	2	4			3

链表方法：

1	-->	2	-->	4	-->	5	^
2	-->	1	-->	3	-->	5	^
3	-->	2	-->	4	^
4	-->	1	-->	3	-->	5	^
5	-->	1	-->	2	-->	4	^

　

3.边目录

如图2

起点	1	1	2	3	4
终点	2	3	4	4	1
长度