图论
?图的基本概念和性质?图的连通性及可达性?图的矩阵表示
?Euler图与Hamilton图?平面图
?对偶图与着色?树与生成树?根树及其应用
2013-7-22
图论
1
图论简介
2013-7-222
图论一、图的基本概念
一个图是一个序偶
V={v1,v(i2=,v1,2,3,3,…,vn…}是一个有限的非空集合,vi,n)称为结点,简称点,V为结点集;
E=e{e1,e2,e3,…,em}是一个有限的集合,i(i=1,2,3,…,m)称为边,E为边集,E中的每个元素都有V中的结点对与之对应。
2013-7-22
图论
3
二、图的类型
1)若边e与无序结点对(u,v)相对应,则称边e为无向边,记为e=(u,v),这时称u,v是边e的两个端点;
2)若边e与有序结点对相对应,则称边e为有向边(或弧),记为e=,这时称u是边e的始点(或弧尾).v是边e的终点(或弧头),统称为e的端点;
2013-7-22
图论
4