一、背景：

1、一笔画问题：手机解锁图案需一笔画出

2、柯尼斯堡七桥问题：

3、现实中的图：

1）计算机网络 2）交通： 3）社交网络

二、图的概念

1、图的定义、相邻与关联

1）图的定义 图可以表示为一个二元组G=<V,E>,其中

V表示非空顶点集，其元素称为顶点（Vertex) E表示边集，其元素称为边(Edge)

e=(u,v)表示一条边，其中u∈V,v∈V，e∈E 2）有向图和无向图

无向图G1=<V1,E1> 有向图G2-<V2,E2>

3)相邻（Adjacent) 边(u,v)连接的顶点u和v相邻

4）关联(Incident) 边(u,v)和其连接的顶点u(或v)相互关联

2、顶点的度与图的度、握手定理

1)顶点的度（Degree of a Vertex） 顶点v的度deg(v)是v关联的边数 2）图的度（Degree of a Graph） 图G=<V,E>的度，是图各顶点的度之和，deg(G)=Σdeg(v) 3）握手定理（Handshaking Lemma) 无向图的度是边数的两倍，deg(G)=2|E| 从而证明柯尼斯堡七桥问题没有解：

3、路径与环路

1）路径(Path) 🖤图中一个的顶点序列<v0,v1,…,vk>称为v0到vk的路径 🖤路径包含顶点v0,v1,…,vk和边（v0,v1),(v1,v2),…,(vk-1,vk） 🖤存在路径<v0,v1,…,vk>，则v0可达vk 🖤如果v0,v1,…,vk互不相同，则该路径是简单的 2）环路（Cycle） 🖤如果路径<v0,v1,…,vk>中v0=vk且至少包含一条边，则该路径构成环路 🖤如果v1,v2,…,vk互不相同，则该环路是简单的 3）有环图和无环图 有环图：图中存在环路 无环图：图中不存在环路

4、连通、连通分量

1)连通（Connectivity） 如果图的任意对顶点互相可达，则称该图是连通的，反之称为非连通

2）连通分量（Connected Components） 根据是否连通将顶点进行分组，相互可达的顶点集称为连通分量

5、子图、生成子图、树、森林

1）子图（Subgraph） 如果V’包含于V，E’包含于E，则称图G’=<V’,E’>是图G的一个子图

2）生成子图（Spanning Subgraph） 如果V'=V,E’包含于E，则称图G’=<V’,E’>是图G的一个生成子图 3）树（Tree） 连通、无环图T=<VT，ET>，树有|VT|-1条边 比如树有9个顶点，有9-1=8条边 4）森林（Forest） 一至多棵树组成的无环图

三、图的表示

1、邻接链表

🖤图G=<V,E>,其邻接链表由|V|条链表的数组构成 每个 🖤每个顶点有一条链表，包含所有与其相邻的顶点

2、邻接矩阵

图G=<V,E>的邻接矩阵由|V|x|V|的二维数组A构成，满足：