图论
1 图论
图论部分 ■第7章图的基本概念 ■第8章一些特殊的图 ■第9章树
2 图论部分 ◼ 第7章 图的基本概念 ◼ 第8章 一些特殊的图 ◼ 第9章 树
第7章图的基本概念 71无向图及有向图 72通路、回路、图的连通性 73图的矩阵表示
3 第7章 图的基本概念 7.1 无向图及有向图 7.2 通路、回路、图的连通性 7.3 图的矩阵表示
71无向图及有向图 无向图与有向图 顶点的度数 握手定理 简单图 完全图 子图 ■补图
4 7.1 无向图及有向图 ▪无向图与有向图 ▪顶点的度数 ▪握手定理 ▪简单图 ▪完全图 ▪子图 ▪补图
无向图与有向图 多重集合:元素可以重复出现的集合 无序积:A&B={(xy)|x∈AyEB 定义无向图G=<V,E>,其中 (1)≠为顶点集,元素称为顶点 (2)E为Ⅳ&的多重子集,其元素e 称为无向边,简称边 例如,G=<V,E>如图所示, 其中{2v2,…, E={(v1,1),(v1,2),(以2,3),(以2,3),(以2,v5),(v1,s),(v4,)
5 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: AB={(x,y) | xAyB} 定义 无向图G=<V,E>, 其中 (1) V为顶点集，元素称为顶点 (2) E为VV的多重子集，其元素 称为无向边，简称边. 例如, G=<V,E>如图所示, 其中V={v2 , v2 , …,v5 }, E={(v1 ,v1 ), (v1 ,v2 ), (v2 ,v3 ), (v2 ,v3 ), (v2 ,v5 ), (v1 ,v5 ), (v4 ,v5 )}