08-图论-离散数学讲义-海南大学(共十一讲)
08-图论-离散数学讲义-海南大学(共十一讲)
8.图论Topics in Graph Theory §8.1 图Graphs
G=
V={v
1,v
2
,······,v n} 顶点vertex集。
E={ e | e=( v
i , v
j
), v
i
,v
j
∈V, v i≠v j}无向边edge集。
γ(e)={ v i, v j}, e的端点end points集。
简写为G＝（V，E）。
TD(v i)顶点v i的度数degree：连接到v i的边的条数。连接一个顶点的圈loop算两度。
孤立点isolated vertex：度数为0的点。
两个顶点相邻adjacent：有一边相连。
定理1. (握手定理) TD＝ TD(v i)=2m.
推论. 任意图的奇数度顶点必有偶数多个。
完全图complete graph：
任意两点都相邻简单图。
定理2. n个顶点的完全图有n(n-1)/2条边。正则图regular graph：每个顶点都有相同的度数。E={
有向边
v i 起点弧尾， v j 终点弧头
TD(v i ):顶点的度degree: 以v i 为端点的边的数目。 OD(vi): 出度, 以v i 为起点的边的数目。 ID(v i ): 入度，以v i 为终点的边的数目。 TD(v i )= OD(vi)+ ID(v i )
OD=ID, TD=2|E|，E| =1/2*TD
TD OD ID 为整个图的总度,出度,入度数。
路径path ： v i ······v j ， 以v i 为起点v j 为终点的顶点序列，相邻顶点相邻。
路径的长length : 路径上边的数目，
简单路径simple path :点都不重复的路径，
回路circuit : 首尾相接的路径，
简单回路simple circuit : 除起点和终点以外都不重复的路径，
v i v j 连通connected : 有路径 v i ······v j 相连。
连通图: 任意两点都连通的图。 例
左图a,c,d,g 是简单路径 右图a,d,b,c,e 是简单路径。 f,e,a,d,b,a,f 是简单回路。 f,e,d,c,e,f 不是简单回路。
b
f
g
d c e
a f d
c
a e b
有向图
v i v j强连通v i v j连通v j v i也连通，
强连通图任意两点都强连通。
子图和商图Subgraph and Quotient Graph
G=(V, E), G’=(V’, E’)
如果V’ ?V, E’ ?E , 就称G’是G的子图subgraph。
G'＝(V, E\E’), G的边集中去掉E’的边。
G’的补图：
G e＝（V，E’）, E’=E\{e}.
连通分量connected components:
一个图的极大连通子图。
一个图可以划分成几个不相交的连通分量。
强连通分量strong connected components: 一个有向图的极大强连通子图。
商图quotient graph
R是V上等价关系，
V/R={[v] | v∈V}
E/R={([v], [w]) | [v], [w]中有相邻的顶点}
G R＝G/R=(V/R, E/R),称为G模R的商图。
把R相关的顶点粘合成一点，相关的边粘合成一边，就得到商图。
连通图的生成树spanning tree: 含有所有顶点的极小连通图.
n个顶点连通图至少有n-1条边。
m条边的连通图去掉m－n＋1条边可以得到生成树。
从连通图中如有回路，去掉回路中的一条边，继续直至没有回路，就得到生成树。
从m条边的连通图中得到生成树，要去掉m－n＋1条边
T是连通图G的生成树，G的每一条不属于T的边e，叫弦。
m条边的连通图共有m－n＋1条弦。
基本回路：每条弦加到T中得到一个回路，叫基本回路。
m条边的连通图共有m－n＋1个基本回路。
割集：G 的边集，去掉后G 不连通。 一条边组成的割集叫桥bridge 。 树的每条边都是桥。
基本割集：生成树T 中每一条边，和G 中对应于T 的所有的弦，组成一个割集，叫基本割集。
最小生成树：权重最小的生成树。 带权的边：带边长的边。 带权的图：每边都带权。 Prim 算法： 设 G=
1. 令 U={v 0}, T={ }.
2. 对任意u ∈U, v ∈V-U, (u,v)∈E, 找到权最小的边(u 1,v 1),
令U=U ∪{v1}, T=T ∪{(u 1,v 1)} 3. 重复2，直至U=V .
得到 T 就是最小生成树。
T 中共有n-1条边
C
B E A
F
D
653
6
4
521
56
C
B E
A
F
D
653
6
4
521
56
U={A}, T={(A,C)}
U={A,C}, T={(A,C),(C,F)}
U={A,C,F}, T={(A,C),(C,F),(D,F)}
U={A,C,F,D}, T={(A,C),(C,F),(D,F),(B,C)}
U={A,C,F,D,B}, T={(A,C),(C,F),(D,F),(B,C),(B,E)}U={A,C,F,D,B,E}
C
B E A
F
D
653
6
4
521
56
(B,E)
(B,C)(D,F)(C,F)(A,C)T E
B B 3 0
D 0
F 0
F 2C C 4C 60
C 5
A A 5A 1A 60
U F E D C B A 定义数组closeEdge[n]
纪录每点到U 的最短距离(点，距离)U 中点距离为0，
每加入一个新点，数组更新一次
template
struct MiniCostEdgeInfo { T adjvex ;int lowcost ;};
template
int operator <(MiniCostEdgeInfo
MiniCostEdgeInfo
{
return a.lowcost template int minimum(MiniCostEdgeInfo if(a[i].lowcost!=0) break; int min=i; for(i=min+1;i if(a[i].lowcost!=0&&a[i] min=i; return min; } template T GetVertex(Graph { int i, n=G.NumberOfVertices( ); if(pos<0||pos>=n) {cerr<<"There are not so many vertices!"; return 0; } VertexIterator i = 0; while(!liter.EndOfList( ) &&i!= pos) { i++; liter.Next( ); } return liter.Data( ); } template void MiniSpanTreePrim(Graph< T> G) { int j,k,l,n=G.NumberOfVertices( ); MiniCostEdgeInfo< T> * closeEdge; closeEdge=new MiniCostEdgeInfo< T>[n]; T s,w, v=GetVertex(G,0); closeEdge[0].lowcost=0;//起始点v 加进U for(int i=1;i { w=GetVertex(G,i); l=G.GetWeight(v,w); closeEdge[i].adjvex=v; if(l>0)closeEdge[i].lowcost=l; else closeEdge[i].lowcost=maxint; } for( i=1;i {k=minimum(closeEdge,n); //确定closeEdge中最小值v=closeEdge[k].adjvex;//取出这一边 w=GetVertex(G,k); l=closeEdge[k].lowcost; cout<<“\n”< closeEdge[k].lowcost=0; //将w加进U for(j=0;j { v=GetVertex(G,j); l=G.GetWeight(w,v); if(l>0&&l { closeEdge[j].lowcost=l; closeEdge[j].adjvex=w; } } } } void main( ) { Graph G.ReadGraph("sctest.dat"); ConnectedComponent(G); MiniSpanTreePrim(G); } Kruskal 克鲁斯卡尔算法 G=(V,E) 连通图 令T=(V,{ }) 是G的所有顶点而无边的非连通图。 1.选择E中权值最小的边， 若该边连接T的两个连通分量，将它加入T, 这时T的连通分量减少1； 否则选下一条权值最小的边。 2.重复1 n-1次直到T连通。 T 就是最小生成树 §8.2 欧拉路径和欧拉回路 哥尼斯堡七桥问题。一笔画问题。 欧拉路径Eular path：通过图的所有边，每个边恰好一次的路径。 欧拉回路Eular circuit：构成回路的欧拉路径。 定理1. G有欧拉回路当且仅当G连通且没有奇数度顶点。 定理2. G有欧拉路径当且仅当G连通且至多有两个奇数度顶点。 §8.3 Hamilton路径和Hamilton回路 周游世界问题：每个城市访问一次只经过一次。 Hamilton公爵提出是否存在一条回路通过正二十边形每个顶点恰一次。 一个连通图G Hamilton路径: 经过每个顶点恰一次的路径。 Hamilton回路：经过每个顶点恰一次的回路。 Hamilton图：有Hamilton回路的图。 完全图Kn，n>2，是Hamilton 图。归纳可证。 n个顶点的连通图G有Hamilton回路，G至少有n条边。 用p(G)表示图G的连通分量的个数。 定理1. G＝(V,E)是Hamilton图，则对任意V1 V, p(G-V1)≤|V1|. 证明：设C是G的一个Hamilton回路，V1都在C上。回路C中去掉V1中顶点，至多划分成|v1|段。因此p(C-V1)≤|V1|. 例1. 下图不是Hamilton图。 引理2. n阶简单无向图G中， l：a……v i v j……b，是一条有m个顶点的路径。a，b只与l中顶点相邻，D(a)+D(b)≥m。则l中所有顶点构成回路。 证明. 若a，b相邻，a……v i v j……b是回路。 设a，b不相邻。D(a)=s, D(b)=t. s+t≥m。t≥m－s。 l中存在相连顶点v i，v j，a v j相邻，b v i相邻， av j……bv i……a构成一个回路。 定理3. n阶简单无向图G中，n>2,任意两个不相邻顶点的度数之和大于等于n－1，则G有Hamilton路径。 证明. 取G中最长路径： l：a……v i……v j……b。 我们证明其长度为n－1，包含G的所有顶点，否则一定可以加长。 a，b不与l外的顶点相邻，否则l可以加长。 设l的长度≤n－2，l上共有顶点少于n－1个。a,b度数和大于n－1，由引理1. l的所有顶点组成回路。 这时有一顶点c不在l上，c c必与l中一点v i相邻。 我们得到含有顶点c，和l中所有顶点的路径，长度比l更长。 推论4. n阶简单无向图G中，n>2,任意两个不相邻顶点的度数之和 大于等于n，则G有Hamilton回路。 证明. 由定理3，G有Hamilton路径。由引理2，这条路径可以构成一条Hamilton回路。 推论5. n 阶简单无向图G 中， n>2,任意顶点的度数大于等于n/2，则G 有Hamilton 回路。 定理6. G 有n 个顶点，m 条边，如果2 1m n 3n 62 ≥（－＋），则G 是Hamilton 图。 证明. 任取不相邻的两个顶点u ，v ∈G ， G 中去掉u ，v 后导出子图G ’, G ’有n －2个顶点，至多2n 2 (n 2)(n C 2 －－－3)＝条边。 u ，v 到G ’的边数有 2n 2 n 3n 6(n 2)(n m C n 22 ≥2－－＋－－3)－－＝D(u)+D(v)≥n. 由推论4.G 是Hamilton 图。 §8.4 运输网络Transport Networks §8.5 匹配问题Matching Problem 二部图、偶图 Bipartite Graph ： 无向图G ＝(V ,E), V= V 1∪V 2，V 1∩V 2＝?。 V 1中顶点互不相邻， V 2中顶点互不相邻，任意边连接V 1，V 2中各一个顶点。 G=( V 1,V 2 ,E). 完全二部图：V 1中每个顶点与V 2 中每个顶点都相邻。 | V 1|=m , | V 2|=n ,完全二部图记做K m,n 。 K 2,3, K 3,3. 定理1.二部图中没有奇数长的回路。 左边两图同构是K2,3，右边都是K3,3. E*?E. E*中的边互不相连，称E*为G的一个匹配。边数最大的匹配叫最大匹配。邻接V1或V2中所有顶点的匹配叫完全匹配。|V1|=|V2|时，完全匹配也叫完美匹配。 定理2. （Hall定理） 设G=( V1,V2 ,E),|V1|≤|V2|. G中有完全匹配iff V1中任意k个顶点至少与V2中任意k个顶点相邻，即，任意X? V1，|X|≤|R(X)|，R(X)为与X中顶点相邻的顶点的集合。 证明. ?是显然的。 ?对V1中顶点个数归纳： | V1|=1是显然的。 设| V1|=k时定理成立。 | V1|=k＋1： 1）如果V1中任意k个顶点都至少与V2中k＋1个顶点相邻，从G中去掉一条边，V1中任意k个顶点都至少与V2中k个顶点相邻，存在完美匹配。 2）如果V1中存在k个顶点只与V2中k个顶点相邻，例如{a1,a2,……，a k}?V1，{b1,b2,……，b k}?V2， {a1,a2,……，a k}只与{b1,b2,……，b k}相邻。 则V1－{a1,a2,……，a k}任意s个顶点，都与V2－{b1,b2,……，b k}中s个顶点相连。 两部分都有完美匹配。 推论3.二部图G＝(V1,V2,E)中如果 （1）V1中每个顶点至少与V2中t条边相邻。 （2）V2中每个顶点至多与V1中t条边相邻。 则G有完美匹配。 证明. V1中任意k个顶点的总度数≥kt。 V2中任意k个顶点的总度数≤kt。 V1中任意k个顶点至少与V2中k条边相邻。 由Hall定理，G有完美匹配。 推论4. 正则二部图必有完美匹配。 §8.6 染色图Coloring Graphs 平面图planar graph a graph can be drawn in a plane so that no edges cross except at vertices K5, K3,3不是平面图 平面图的面：内部面，外部面， 有限面，无限面。 面的边界：包围这个面的回路（不一定是简单回路）。 面的次数次数deg(R)=边界的长度。 非连通平面图有一个公共外面，边界由k个回路组成，k＝p(G). 平面图每条边都是两个面的交线。 一条边处于一个内部面中或一个外部面中，面的次数要计算两次。 定理1. 平面图的所有面的次数之和等于边数的两倍： i i deg(R )2m =∑ 极大平面图：简单平面图，增加一边就不是平面图。 极小非平面图：简单非平面图，减少一边就是平面图。 定理2. n 阶极大平面图的性质： （1） 连通。 （2） n ≥3时，每个面R i ，deg(R i )=3. （3） n ≥4时，每个顶点v ：D(v)≥3。 定理3. 欧拉定理：满足n －m ＋r ＝2， 任意连通平面图G ，满足n －m ＋r ＝2， 即，顶点数－边数＋面数＝2。 证明. 对边数归纳： m ＝0，1，2，3显然。 增加一边：增加一个顶点，不增加面。 不增加顶点，增加一面。 推论4. 任意连通度为k 的平面图G ，满足n －m ＋r ＝k ＋1。 不满足欧拉公式的简单图不是平面图。 请验证K 5，K 3,3，不是欧拉图。 定理5. 设G 是连通平面图，每个面的次数至少l ，（l ≥3），则m ≤ (2)2 l n l --。 证明. 2m ≥l r ， n －m ＋r ＝2， l n －l m ＋2m ≥ l n －l m ＋l r ＝2l ， l m －2m ≤l n －2l m ≤ (2)2 l n l --。 定理6. 简单连通平面图G 中至少有一点v ， D(v)≤5. 证明. 假设任意顶点v ，D(v)≥6. 6n ≤2m ，3r ≤2m 3n ≤m n －m ＋r ＝2 6＝3n －3m ＋3r ≤m －3m ＋2m ＝0 这不可能。 定理7.（库拉图斯基定理） 一个图G 是平面图当且仅当G 没有可以收缩到K 5或K 3,3的子图。 每个凸多面体都可以映射到平面图。 定理8. 正多面体只有正4，6，8，12，20面体五种。 证明. 设G 是一个正多面体，n 个顶点，m 条边，r 个面，每个顶点d 度，每个面l 次。 由定理6，3≤d ≤5。l ≥3。 dn ＝2m ，l r=2m ＝dn. n －m ＋r=2， 2l n －2l m ＋2l r=4l ， 2l n－d l n＋2dn=4l， n=4 l /(2l－d l＋2d)， 1）d＝3. n=4l/(6－l) l=3, n=4, m=6, r=4. 正四面体 l＝4，n＝8，m=12, r=6, 正六面体. l＝5，n＝20，m=30, r=12, 正12面体 2）d＝4. n=2 l /(4－l). l =3, n=6, m=12, r=8, 正八面体。 3）d＝5. n=4 l /(10－3l). l＝3，n＝12，m＝30，r＝20 正20面体。 对偶图： 设G＝(T,V)是平面图， （1）G的每个面R i中取一点v i*， V*={v1*，v2*，……，v r*} （2）若两个面R i，R j有公共边界e k，连接v i*，v j*，得到边e k*，E*={ e1*，e2*，……，e m*} 则得到G*=(V*,E*)称为G的对偶图。 G和G*边数相同，m*＝m; G的面数等于G*的顶点数，n*=r; G连通，则G的顶点数等于G*的面数, r*=n. G不连通，则G的顶点数等于G*的面数, r*=n－p(G)＋1. G和G*不同构，同构图的对偶图不一定同构。G**不一定同构于G。 不连通图的对偶图连通，连通图的对偶图连通。 若G G*，就称G是自对偶的图。 染色图colouring Graph 一个图用彩色将每个顶点着色，相邻顶点染不同颜色。 一个平面图用彩色将每个面着色，相邻面染不同颜色。只要换成其对偶图即可。平面图G最少用k种颜色染色，就称为k色图。 k称为chromatic number of G. 记做χ(G) 四色定理：任何一个平面图都是四色图。 染色多项式chromatic polynomial 用n种颜色染一个图，有多少不同的方法,记做P G(n). P G是一个多项式函数，称为chromatic polynomial of G. 例4. 设L4是4个顶点的一条线。用x种颜色，第一点，x种方法着色，第 二点x－1种方法着色。第三第四点都是x－1。 P L4(x)=x(x-1)3. χ(L4)＝2。 例5．P Kn(x)＝x(x-1)(x-2)……(x-n+1)=[x]n. χ(K n)＝n。 定理1. 设G1，G2，……，G m是G的连通分量，则P G(x)= P G1(x) P G2(x)……P Gm(x)。 χ(G)＝max{χ(G1), χ(G2),……，χ(G m)} 例6. G是两个不相连三角形，P G(x)= x2(x-1)2(x-2)2. 例7. G是n个不相连顶点，P G(x)=x n。 G e是G去掉e导出的子图，Ge是将e的两端点粘合得到的图。 定理2. P G(x)＝P Ge(x)－P G e(x) 证明. 设e的端点为a，b。G着色必须将ab着不同色。G e着色必须将ab着同色。 G e着色a，b可着同色，可着不同色。 P Ge(x)＝P G(x)+P G e(x). e 例G如下图。 P Ge(x)=x2(x-1)2(x-2)2, P G e(x)= x (x-1)2(x-2)2, P G(x)= P Ge(x)－P G e(x) =x2(x-1)2(x-2)2－x (x-1)2(x-2)2 ＝x (x-1)3(x-2)2, χ(G)=3, G是3色图。 引理3. 设G是简单图，G已染色，相邻顶点颜色不同。G中染色αβ两种颜色的顶点 导出子图为G αβ.交换G αβ 中一个连通分量中染色α和β，G仍然保持相邻顶点 不同颜色。 证明.G中任意相邻两点a，b. b? Gαβ，或a，b∈Gαβ，或a∈Gαβ且b? Gαβ，a，b染色仍然不同。 定理4（五色定理） G是任意一个平面图,则χ(G)≤5。 证明.对G的顶点个数归纳。G中至少有一点a，D(a)≤5。 归纳假设去掉a，导出的子图G’可以用5重颜色着色。 如果a只与G’中4个点相邻，a可以用第五种颜色着色。 如果a与G’中5个点相邻，但5点中有重复颜色，a可以用第五种颜色着色。假设a与G’中5个点相邻，5点着色各不相同，5点分别是b1，b2，……，b5。 设b1着色α，b2着色β，而b1，b2，不在G αβ 的同一个连通分量中。由引理3，交换b3所在分量中颜色α和β，可以使b1，b3着色相同。这时a可着色。 设b1着色α，b3着色β，而b1，b3在G αβ 的同一个连通分量中。这时b1到b2有一条着色αβ相间的链。与a形成一条回路，组成一个面。b2在这个面的内部或在外部。 如果同样b2，b4；b3，b5；b3，b5；b2，b5；b1，b4都有一个这样的链，相互交叉。这时a，b1，b2，b3，b4，b5组成一个K5。与G是平面图矛盾。这是不可能的。 海南大学2010-2011学年度第2学期试卷 科目：《物理化学C 》试题(A 卷) 适用于 高分子材料与工程、材料科学与工程、生物工程、制药 专业 姓名： 学 号： 学院： 专业班级： 阅卷教师： 年 月 日 考试说明：本课程为闭卷考试，可携带 计算器 。 一、判断题（每小题1分，共10分，对的在括号里打“√”， 错的打“×”） 1、在一定温度下，一定量的理想气体进行可逆膨胀过程，其对外做最大功。 （ O ） 2、功和热都是途径函数，对应某一状态有一确定值。 （ X ） 3、H 2和O 2经绝热恒容反应，此过程的ΔU 、ΔH 、ΔA 、ΔG 均不为0。 （ X ） 4、基于热力学第二、三定律，某气体的规定熵S m > 0。 （ O ） 5、标准平衡常数K θ的数值只与温度有关，与反应平衡系统的总压及组成无关。 （ O ） 6、在110℃及101.325kPa 下，水的化学势大于水蒸汽的化学势。 （ O ） 7、阿伦尼乌斯方程式主要是研究浓度对反应速率的影响。 （ X ） 8、一定条件下，某反应的m r G >0，所以要选用合适的催化剂，使反应得以进行。 （ X ） 9、溶胶系统是高度分散的多相系统，是热力学的不稳定系统。 （ O ） 10、胶体系统产生丁铎尔现象的原因是胶粒带电所引起的。 （ X ） 二、选择题（每题2分，共20分 选择正确答案的编号，填在各题前的括号内） 1、在恒压、绝热、w ′=0的条件下，发生某化学反应，使系统的温度上升，体积变大，则此 过程的ΔH （ = ）；ΔU （< ）。选择填入： A 、> 0 B 、= 0 C 、< 0 D 、无法确定 2、在相同温度条件下，大液滴分散成小液滴后，其饱和蒸气压将（ C ） A 、变小 B 、不变 C 、变大 D 、无法判断 3、0℃ 5个大气压下，H 2O(S)→H 2O(1)其体系熵变（ A ） A 、ΔS 体>0 B 、ΔS 体<0 C 、ΔS 体=0 4、合成氨反应N 2(g)+3H 2(g) == 2NH 3(g)，达到平衡后，加入惰性气体，且保持体系温度，总 压不变（气体为理想气体），则（ B ） A 、平衡向右移动 B 、平衡向左移动 C 、平衡不受影响 5、通常称为表面活性剂的物质，是指当其加入少量后就能 C 的物质。 A 、增加溶液的表面张力 B 、改变溶液的导电能力 C 、显著降低溶液的表面张力 D 、使溶液表面发生负吸附 6、某反应的总的速率常数与各基元反应的速率常数有如下关系：k=k 2(k 1/k 3)1/2，则表观活化 能与基元反应的活化能关系为 ( C ) A 、E a =E 2+21E 1- E 3 B 、E a = E 2 +( E 1- 2E 3)1/2 C 、E a = E 2 +2 1(E 1- E 3) 7、两反应均为一级的平行反应A )2() 1(21C k B k ，B 为所需产物，而C 为副产物，已知两反应的指 前因子A 1=A 2，E a1=100KJ ·mol -1，E a2=70KJ ·mol -1，今欲加快反应(1)的反应速度，应 A 。 A 、提高反应温度 B 、降低反应温度 C 、升高压力 D 、降低压力 8、胶体系统的电泳现象表明 D 。 A 、分散介质不带电 B 、胶体粒子处于等电状态 C 、胶团带电 D 、胶体粒子带有大量的电荷 9、在农药中通常都要加入一定量的表面活性物质，如烷基苯磺酸盐，其主要目的是 D 。 A 、增加农药的杀虫药性 B 、消除药液的泡沫 离散数学图论与系中有图题目 ————————————————————————————————作者：————————————————————————————————日期： 图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1) 离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝ 图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 离散数学的基础知识点总结 第一章命题逻辑 1.前键为真，后键为假才为假；＜—＞，相同为真，不同为假；2?主析取范式：极小项（m）之和；主合取范式：极大项（M）之积； 3.求极小项时，命题变元的肯定为1，否定为0,求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写; 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有2n个极小项或极大项，这2n为（0~2n-1）刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法（=＞）:真值表法；分析法（假定前键为真推出后键为真，假定前键为假推出后键也为假） 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第二章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含T,存在量词用合取“； 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0; 2.基：集合A中不同元素的个数，|A|; 3.幕集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幕集P(A)有2°个元素，|P(A)|= 2|A|= 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔AXB的基数为mn , A到B上可以定义2mn种不同的关系； 2.若集合A有n个元素，则|A X\|= n2, A上有2n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全圭寸闭环的性质：自反性，对称性，反对称性，传递性； 4.前域（domR）:所有元素x组成的集合； 离散数学11春图论部分综合练习辅导 大家好！本学期的第二次教学辅导活动现在开始，本次活动主要是针对第二单元图论的重点学习内容进行辅导，方式同样是通过讲解一些典型的综合练习作业题目，帮助大家进一步理解和掌握图论的基本概念和方法． 图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法．教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等． 本次综合练习主要是复习这一单元的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题．这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习． 下面是本学期第4，5次形考作业中的部分题目． 一、单项选择题 单项选择题主要是第4次形考作业的部分题目． 第4次作业同样也是由10个单项选择题组成，每小题10分，满分100分．在每次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩．需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目． 1．设图G ＝ 模拟静电场 【实验目的】 1.学习模拟实验方法及用电压表与检流计测绘等势线。 2.加强对电场强度和电位概念的理解，了解电力线与等势线之间的关 系。 3.测绘同轴圆电缆及平行导线的等势线和电力线。 【实验原理】 1.为何用模拟法测绘 了解带电体周围的电场分布情况对研究电子束及其它带电粒子在电场中的运动是必须的。计算经典电场分布通常是很困难的。大多数情况下只有数值近似解，而用实验方法来测绘电场分布情况比较容易。然而直接测量静电场也存在很大困难。通常保持一个恒定的静电场本身就比较困难。再者，由于测量探针的引入会因静电感应而改变原被测电场。因此，在实验中通常用稳恒电流产生的电场来模拟静电场，其理由是 （1）稳恒电源可建立稳定的电场 （2）探针的引入不会改变原来的电场分布 （3）稳恒电流的电场分布和静电场分布完全一样。 2.稳恒电流电场与相应电场的等效性 我们在实验中用同轴圆电缆的电场分布来模拟圆筒状电容器的电场分布，而用平行直导线的电场分布来模拟二个带异种电荷的点电荷的电场分布。我们首先要证明这两种电场分布的等效性。导体A与B的圆柱，分别带等量异种电荷。A、B间为真空时 r处的电场强度为: 距中心 r处的电势为： 如果A、B之间充满一种电阻为R的导体，A、B分别与电池正负极相连接。 r处的电场强度为: 距中心 r处的电势为： 3.实验方法： 测量电势比较方便。所以先测绘等势线。这里使用两种测量等势线的方法：一是电压表方法，它可以直接测出导电纸上某一点的电势（即与另一参考点的电势差），其优点在于方便、直观，并且所测电势可连续变化。第二种方法是检流计法。它的优点在于测量精度较高。 【实验仪器】 静电场等位仪, 电阻箱 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 海南大学２0１0-20１1学年度第２学期试卷 科目:《物理化学C 》试题(A 卷） 适用于 高分子材料与工程、材料科学与工程、生物工程、制药 专业 姓名： 学 号： 学院: 专业班级: 阅卷教师： 年 月 日 考试说明：本课程为闭卷考试,可携带 计算器 。 一、判断题（每小题1分,共10分，对得在括号里打“√”,错得打“×”） 1、在一定温度下,一定量得理想气体进行可逆膨胀过程，其对外做最大功. （ ) ２、功与热都就是途径函数,对应某一状态有一确定值。?? （ ) ３、H ２与O 2经绝热恒容反应,此过程得ΔU 、ΔH 、ΔA 、ΔG 均不为0。 ( ） 4、基于热力学第二、三定律，某气体得规定熵Ｓｍ 〉 0。 ( ) ５、标准平衡常数 K θ得数值只与温度有关,与反应平衡系统得总压及组成无关。 （ ) ６、在110℃及１ 01、325kPa 下，水得化学势大于水蒸汽得化学势。 ( ) 7、阿伦尼乌斯方程式主要就是研究浓度对反应速率得影响. ( ） 8、一定条件下,某反应得〉0，所以要选用合适得催化剂,使反应得以进行。 ( ) 9、溶胶系统就是高度分散得多相系统，就是热力学得不稳定系统。 ( ） 10、胶体系统产生丁铎尔现象得原因就是胶粒带电所引起得。 ( ） 二、选择题(每题２分，共20分 选择正确答案得编号,填在各题前得括号内) ′=0得条件下，发生某化学反应，使系统得温度上升，体积变大，则此过程得ΔH( ）;ΔＵ（ ）。选择填入: Ａ、〉 0? B 、= 0? C 、< 0? ? D 、无法确定 2、在相同温度条件下，大液滴分散成小液滴后，其饱与蒸气压将（ ） Ａ、变小?? B 、不变 Ｃ、变大 ?D 、无法判断 3、０℃ 5个大气压下，H 2O(Ｓ)→H ２O （1）其体系熵变( ) A 、ΔS 体＞0 ?B 、ΔS 体＜0? ?C 、ΔS 体＝０ ４、合成氨反应N ２（ｇ)＋3H ２(g) == ２NH 3(g ），达到平衡后,加入惰性气体，且保持体系温度，总压不变（气体为理想气体)，则（ ） A 、平衡向右移动 B 、平衡向左移动 C 、平衡不受影响 5、通常称为表面活性剂得物质,就是指当其加入少量后就能 得物质。 A 、增加溶液得表面张力 ???B 、改变溶液得导电能力 Ｃ、显著降低溶液得表面张力? ?D 、使溶液表面发生负吸附 6、某反应得总得速率常数与各基元反应得速率常数有如下关系：k=k 2（k 1/k 3）1/2，则表观活化能与基元反应得活化能关系为 （ ） A 、E a =E 2+E 1- E ３ B 、E a = E 2 +（ Ｅ１- 2E 3）1/２ C 、E a ＝ E 2 +(E 1- E 3) ７、两反应均为一级得平行反应 A ，Ｂ为所需产物，而C 为副产物,已知两反应得指前因子A 1＝A ２，Ｅa1=100KJ ·mo ｌ—1,E ａ2=70K Ｊ·m ｏl －１，今欲加快反应(1)得反应速度，应 。 A 、提高反应温度? ? ? B 、降低反应温度 C 、升高压力? ?? ??D 、降低压力 8、胶体系统得电泳现象表明 . A 、分散介质不带电 ? ? B 、胶体粒子处于等电状态 C 、胶团带电?? ??D 、胶体粒子带有大量得电荷 9、在农药中通常都要加入一定量得表面活性物质,如烷基苯磺酸盐，其主要目得就是 . A 、增加农药得杀虫药性 B 、消除药液得泡沫 C 、防止农药挥发???? D 、提高农药对植物表面得润湿能力 10、在化学动力学中，质量作用定律只适用于 . A 、反应级数为正整数得反应???B 、基元反应 C 、?恒温恒容反应 ?? D 、理想气体反应 三、填空题：（每题2分，共２0分)在以下各小题中画有__＿ ____处填上答案. 1律得数学表达式就是 ，其实质上就是 。 2、拉乌尔定律得数学表达式为 ，亨利定律得数学表达式 光的干涉—牛顿环 【实验目的】 1、 了解牛顿环等厚干涉的原理和观察方法 2、 利用干涉方法测量平/凸透镜的曲率半径 3、 掌握读数显微镜的调节和使用 4、 学习用逐差法和图解法处理数据，并比较两种处理结果 【实验原理】 通常将同一光源发出的光分成两束光，在空间经过不同的路程后合在一起产生干涉。 牛顿环是典型的等厚干涉现象 牛顿环实验装置通常是由光学玻璃制成的一个平面和一个曲率半径较大的球面组成， 在两个表面之间形成一劈尖状空气薄层。以凸面为 例，当单色光垂直入射时，在透镜表面相遇时就会 发生干涉现象，空 气膜厚度相同的地方形成相同的干涉条纹，这种干涉称作等厚干涉。 在干涉条纹是以接触点为中心的一系列明暗相间的同心圆环，称牛顿 环。 牛顿环的形成： 由于透镜表面B点处的反射光1和玻璃板表面C点的反射光2在B点出发生干涉，在该处产生等厚干涉条纹。按照波动理论，设形成牛顿环处空气薄层厚度为d，两束相干光的光程差为： △=2d + λ/ 2 = kλ 当适合下列条件时有 △ =2d + λ/ 2 = kλ ---------（1） ( K = 1，2，3，... 明△ =2d + λ/ 2 = (2k+1)λ/2---------（2） ( K = 1，2，3，... 暗式中λ为入射光的波长，λ/2 是附加光程差，他是由于光在光密介质面上反射时产生的半波损失而引起的 ）表明，当 K=0 时（零级），d=0，即平面玻璃和平凸透镜接触处的条纹为暗纹。光程差Δ仅与d 有关，即厚度相同的地方干涉条纹相同。 平凸透镜曲率半径的测量： 由几何关系，在B点可得：r2=R2-(R2-d2)=2Rd-d2 因为 R>>d 所以得 上式表明d 与 成正比，说明离中心越远，光程差增加越快，干涉条纹越来越密。 由公式： ... (暗环) 可知 若测出第K级暗环的半径 ，且单色光的波长已知时，就能算出球面的曲率半径R 。但在实验中由于机械压力引起的形变以及球面上可能存在的微小尘埃，使得凸面和平面接触处不可能是一个理想的点，而是一个不很规则的圆斑，因此很难准确测出比较简单的方法是测量距中心较远处的牛顿环直径。 以暗环为例，当测得较远的第K级和第K+M级的暗环直径 第四篇图论 自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题。如迷宫问题、匿门博奕问题、棋盘上马的路线问题、四色问题和哈密顿环球旅行问题等，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。 1847年克希霍夫（Kirchhoff）第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。尤其在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。 图论研究的课题和包含的内容十分广泛，专门著作很多，很难在一本教科书中概括它的全貌。作为离散数学的一个重要内容，本书主要围绕与计算机科学有关的图论知识介绍一些基本的图论概论、定理和研究内容，同时也介绍一些与实际应用有关的基本图类和算法，为应用、研究和进一步学习提供基础。 第4-1章无向图和有向图 学习要求：仔细领会和掌握图论的基本概论、术语和符号，对于图论研究的一些最基本的课题，如道路问题、连通性问题和着色的问题等，应掌握主要的定理内容和证明方法以及基本的构造方法，以便为下一章研究提供理论工具。学习本章要用到集合和线性代数矩阵运算的知识，特别是集合数和矩阵秩的概念。 §4-1-1 图的基本概念 图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的方法也可以用来描述其它的问题。当我们考察全球航运时，可以用点来代表城市，用线来表示两城市间有航线通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道；当研究物质的化学结构时，可以用点来表示其中的化学元素，而用线来表示元素之间的化学键。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图形的这种表示方式中可以抽象出图的数学概念来。 一、图 定义4-1-1.1一个（无向）图G是一个二元组（V（G），E（G）），其中V （G）是一个有限的非空集合，其元素称为结点；E（G）是一个以不同结点的无序对为元素，并且不含重复元素的集合，其元素称为边。 我们称V（G）和E（G）分别是G的结点集和边集。在不致引起混淆的地方，常常把V（G）和E（G）分别简 图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: A&B={(x,y) | x∈A∧y∈B} 定义无向图G= 通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用e k表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E=? 平凡图: 1 阶零图 空图: V=? 顶点和边的关联与相邻：定义设e k=(v i,v j)是无向图G= 离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ 图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ? ? ? ? ? c a b e d ? f 图四 图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8 个结点的三次正则图 (2) (1) (3) (2) (1) 大学物理实验 教学参考资料 1.海南大学物理实验中心网址： http://210.37.37.223/ 2.海南大学网络教学平台：https://www.sodocs.net/doc/061605111.html,/大学物理C(陈文钦）： https://www.sodocs.net/doc/061605111.html,/eol/homepage/common/opencourse/co urse/layout/page/index.jsp?courseId=6058 3.百度文库：https://www.sodocs.net/doc/061605111.html,/ 4.爱问共享资料： https://www.sodocs.net/doc/061605111.html,/搜索 “海南大学物理实验绪论” “海南大学物理实验教案” 大学物理实验 网络教学平台 (https://www.sodocs.net/doc/061605111.html,) 大学物理实验大学物理实验 大学物理实验 https://www.sodocs.net/doc/061605111.html, 学号 000000 大学物理实验 大学物理实验 大学物理实验绪论材料与化工学院材料科学与工程系 大学物理实验室 大学物理实验 ?大学物理实验绪论 ?Ⅰ.为什么要学习大学物理实验课程 ?1、地位和作用2、目的和任务 ?Ⅱ.如何上好大学物理实验课 ?Ⅲ.大学物理实验课程的理论基础(重点) ?1、测量2、有效数字 ?3、误差4、直接测量量的不确定度?5、间接测量量的不确定度6、数据处理 大学物理实验 以诺贝尔物理学奖为例：80%以上的诺贝尔物理学奖给了实验物理学家，20%的奖中很多是实验和理论物理学家分享的；实验成果可以很快得奖，而理论成果要经过至少两个实验的检验才能获奖；有的建立在共同实验基础上的成果可以连续几次获奖。 1、物理实验的地位与作用 Ⅰ. 为什么要学习大学物理实验课程 “物理学是以实验为本的科学”——杨振宁物理理论生产实践 物理实验 大学物理实验 培养能力。观察现象；透过现象研究规律；科学处理实验数据；从复杂的现象中抽取相关信息；运用知识解决实际问题；根据仪器说明正确使用仪器等从事现代科学实验的能力培养作风。实事求是，严肃认真，坚韧不拔，团结协作，爱护公物等 培养素质。实验技能，实验方法和技巧，设计思想良好的实验习惯，严谨的思维，勇于创新等 2、大学物理实验课程的目的和任务 Ⅰ. 为什么要学习大学物理实验课程 第八章图论 例1、下面哪些数的序列,可能是一个图的度数序列?如果可能,请试画出它的图. 哪些可能不是简单图?a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) d) (1,1,1,1,4) e) (1,2, 2,4,5) 解:a)不是, 因为有三个数字是奇数. b) c) d)是. e) 不是简单图,因为它有5个结点, 有一个结点度为5, 必然有环或平行边. 例2、已知无向简单图G中,有10条边,4个3度结点,其余结点的度均小于或等于2,问G中至少有多少个结点?为什么? 解:已知边数|E|=10, ∑deg(v)=2|E|=20其中有4个3度结点, 余下结点度之和为: 20-3×4=8 因为G是简单图, 其余每个结点度数≤2, 所以至少还有4个结点.所以G中至少有8个结点. 强连通、单侧连通和弱连通 在简单有向图G中,如果任何两个结点间相互可达, 则称G是强连通. 如果任何一对结点间, 至少有一个结点到另一个结点可达, 则称G是单侧连通. 如果将G看成无向图后(即把有向边看成无向边)是连通的,则称G是弱连通. 在简单有向图中,具有强连通的最大子图,称为强分图.具有单侧连通的最大子图,称为单侧分图. 具有弱连通的最大子图,称为弱分图. 注：我每次都会被各种分图弄糊涂！！考试时要注意啊，千万不要错了 利用可达性矩阵求强分图，注意初等矩阵变换的知识不要忘了！！ 令图G= 霍尔效应 如果置于磁场中的载流体的电流方向与磁场方向垂直，则在垂直于电流和磁场的方向上会产生一附加的横向电场，称霍尔效应。如今霍尔效应不但是测量电学材料电学参量的主要手段，而且应用于非电量测量、自动控制和信息处理等方面。 二、实验目的： 1. 了解霍尔效应的实验原理以及有关霍尔器件对材料的要求。 2. 学习用“对称测量法”消除负影响，测量试样的V H －I S 曲线和V H －I M 曲线。 3. 确定样品的导电类型、载流子浓度及迁移率。 三、实验原理： 霍尔效应从本质上讲运动的带电粒子在磁场中受洛仑兹力的作用，产生偏转而引起材料表面电势不同。 ---------- A` C` 对于图中所示的半导体试样，若在X 方向通以电流I s 在z 方向上加以磁场B 则在Y 方向即试样AA`电极两侧开始聚积异号电荷而产生相应的附加电场。电场指向取决于试样的导电类型。显然，该电场阻止载流子继续向侧面偏移。 当载流子受横向电场力－eE H 与洛仑兹力B eV F l ?-=相等时，样品两侧电荷的积累就达到平衡，故有： B eV eE H ?-=- （1） 其中E H 为霍尔电场，V 是载流子在电流方向上的平均漂移速度。 设试样的宽为b ，厚度为d 载流子浓度为n ，则 I s ＝nevbd （2） 由（1）、（2）两式可得： V H ＝E H b ＝d B I S H R （3） 比例系数ne H R 1 =称为霍尔系数，它是反映霍尔效应强弱的重要参数，只要测出V H 以及 知道I S B 和d 可用下列计算： 霍尔系数：10?= B I d V R S H H 8 载流子浓度：e R n H 1= 迁移率：S V l I S σμ= 电导率：μσne = 由V H 的符号判断样品的导电类型： 判断的方法是按图一所示的电流和磁场的方向，若测得的V H 的值是正值，样品属N 型，否则，为P 型。 判断时一定要注意到电流、磁场和霍尔电压的值必同时为正时才成立。 霍尔器件对材料的要求： 要得到大的霍尔电压关键是选择霍尔系数大（即迁移率高、电阻率低。半导体迁移率高电阻率适中是制造霍尔元件较理想的材料。由于电子迁移率比空穴迁移率大，所以霍尔元件多采用N 型材料。其次，霍尔电压大小与材料的厚度成反比，因此，薄型的霍尔器件输出电压较片状要高得的多。 四、实验方法： 1.对称测量法： 在产生霍尔效应同时产生各种负效应，如爱庭好森效应、里纪－杜勒克效应和制作工艺（不等势电压降）产生的误差，均可以通过改变输入电流和磁场的方向加以消除，在规定了电流和磁场正反方向后分别测量由下列四组不同方向的电流和磁场的组合的V AA`即 ＋B ＋I S V AA`＝V 1 －B ＋I S V AA`＝－V 2 －B －I S V AA`＝V 3 ＋B －I S V AA`＝－V 4 求V 1 V 2 V 3 V 4代数平均值 V H ＝ 4 4 321V V V V -+- 电导率的测量： 设A 、C 间的距离为L 。样品横截面积为S=bd 流经样品电流为I S 在零磁场下若测行A 、C 间的电位差σV 可求得σ 五、实验内容： M M H S 2.保持I S 值不变I S ＝1.8mV 测绘V H －I M 曲线：海南大学2010——2011物理化学A卷试题、答案
离散数学图论与系中有图题目
离散数学测验题--图论部分(优选.)
离散数学图论练习题
离散数学的基础知识点总结
离散数学图论复习
模拟静电场-大学物理实验-海南大学
离散数学知识点总结
海南大学物理化学期末试题[完整]
光的干涉—牛顿环-大学物理实验-海南大学
离散数学之图论
离散数学第七章图的基本概念知识点总结docx
离散数学图论部分经典试题及答案
离散数学图论与关系中有图题目
海南大学物理实验-绪论
离散数学(图论)课后总结
霍尔效应-大学物理实验-海南大学
相关文档
- (优选)离散数学图论版
- 离散数学(图论)课后总结
- 《离散数学》图论中的各种名词的解释表格整理版
- 离散数学图论习题
- 图论和函数总结梳理离散数学思维导图
- 离散数学 图论基础
- 《离散数学》图论中的各种名词的解释表格整理版
- 离散数学 图论优秀课件
- 离散数学-图论共89页
- 离散数学图论部分经典试题及答案
- 离散数学图论基础知识
- 图论和函数总结梳理(离散数学,思维导图)
- 离散数学图论答案
- 离散数学图论部分经典试题及答案
- 离散数学 图论
- [理学]离散数学第24讲图论
- 离散数学——图论
- 《离散数学》图论中的各种名词的解释 表格整理版
- 离散数学 图论总复习
- 图论和函数总结梳理(离散数学,思维导图)