做商城网站的项目背景图片,台州椒江网站建设公司,论坛网站开发,一个完整的ppt作品一、基本概念
1.一些基本术语#xff1a; 2.点u#xff0c;v邻接#xff08;或相邻#xff09;: 边e称为关联顶点u和v,or e连接u和v;
3.G(V,E)中#xff0c;顶点v所有邻居的集合#xff1a;N(v), 成为v的邻域。
4.度 #xff1a; deg(v)
5.悬挂点#xff1a;度为1的…一、基本概念
1.一些基本术语 2.点uv邻接或相邻: 边e称为关联顶点u和v,or e连接u和v;
3.G(V,E)中顶点v所有邻居的集合N(v), 成为v的邻域。
4.度 deg(v)
5.悬挂点度为1的顶点
6.孤立点度为0的顶点。 二、几个定理and概念
1.握手定理边数的2倍度数。 总度数一定为偶数
2.无向图有偶数个奇数度顶点。 由1. (定理2)
3.入度 ; 出度
4.有向图边数入度出度 (定理3)
5.完全图 , 每个顶点的度n-1
6.圈图
7.轮图 顶点数n1边数2n
8.立方体图 顶点数2^n,边数: n*2^n-1
9.二部图二分图用颜色判断
10.完全二部图
11.从旧图到新图 子图并图等
12.加权图 边上带权重 三、图的表示
1.邻接表 2.邻接矩阵
3.关联矩阵
当ej关联vi时 1or : 0 四、其它概念
1.图的同构
对于G1(V1,E1)G2(V2,E2) 存在映上的从V1到V2 的函数f
f性质对所有a,b a和b在G1里相邻-a和b在G2里相邻。
2.通路从u到v, (边的序列) 长度通路中边的数目 对于权重图则为各边的权重之和。 回路若一条通路在相同的顶点开始和结束且长度大于0则它是一条回路。 若通路或回路不重复的包含相同的边那么它就是简单的。 各边全不同的简单回路 各点全不同的基本回路
3.可达性vi到vj从在通路不管长度。
4.无向图连通性
连通图每一对顶点间都有一条路径
or : 不连通图
5.连通分量是G的连通子图而不是G的其它连通子图的真子图。即G的最大连通子图
6.有向图连通性
1强连通对任意a,b a到b有b到a也有
2弱连通在有向图的基本无向图中是连通的
7.计算顶点间的通路用矩阵相乘。 五、欧拉回/通路 可一笔画出 边不重复
1.欧拉回路 充要 所有顶点度数都为偶数
2.欧拉通路 充要有2个顶点度数为奇数其它为偶数。 六、哈密顿回/通路 点不重复 无充要条件
1.哈回.... (性质) 定理 2....哈
定理 3....哈回
1狄拉克定理 2奥尔定理 例
答mn2; 七、平面图与着色
1.欧拉公式
设G是带e条边和v个顶点的连通平面简单图。设r是G的平面图表示中的面数则 re-v2。
2.图着色
简单图的着色给每个顶点都指定一种颜色使没有两个相邻的顶点颜色相同。
平面图的着色数不超过4
