离散数学(12)

离散数学(12)陈斌[e-mail]2009.12.04目录数理逻辑集合论图论抽象代数●图的基本知识图（graph）由结点和联结结点的边所构成的离散结构结点vertex集V：非空集合边edge集E：多重集合（集合中可能存在相同元素，元素附带一个重数的属性）边集是多重集合表示图可以有多个相同的边图的基本知识边和结点的关系有向边(directededge)用结点的二元有序组表示第一分量称作起点，第二分量称作终点无向边(indirectededge)用结点的两元素多重集表示无向边可以是多重集意味着允许无向环(loop)无向边的端点称作邻接(adjacent)结点图的基本知识abcG=V,EV={a,b,c}E={{a,c},{a,c},{b,c},{c,c}}无向图，有多重边，环abcG=V,EV={a,b,c}E={a,c,c,a,b,c,c,c}有向图，无多重边，有环图的基本知识对于图G=V,E有限图：V,E都是有限集，否则称为无限图重边multipleedge：E中重数大于1的边称为重边（平行边）重图multigraph：边集E中至少有一个元素重数大于1单图：每条边的重数都等于1图的基本知识简单图simplegraph：无环和重边的无向图完全图completegraph：任何两个不同结点间都有边关联的简单图，记做Kn孤立结点isolatedvertex：不是任何边的端点的结点零图：仅有孤立结点构成的图（E=）K2K3K4K5图的基本知识：赋权图赋权图G=V,E,f,g结点权函数：f:V→W边权函数：g:E→WW可以是任何集合，常为实数的子集普通的图研究结点和边之间的拓扑关系邻接，连通，通路，划分等性质赋权图给普通图附加了数量关系距离，成本，代价，规模等性质是GIS应用的基础图的基本知识：赋权图515217420268ABA到B•最短路径？（普通图）•最优路径？（赋权图）图的基本知识：度结点的度(degree)端点v的度d(v)定义为关联端点v的边的数目有向图中，度分为出度(out-degree)和入度(in-degree)出度d+(v)是端点v作为有向边起点的数目入度d-(v)是端点v作为有向边终点的数目有向图中度d(v)=d+(v)+d-(v)例子图的基本知识：度度的性质所有端点度的总和为偶数，而且是边数目的两倍有向图中出度的总和等于入度的总和奇数度结点必为偶数个反证法自然数序列(a1,a2,…an)是某个图的度序列当且仅当序列中所有数的总和为偶数一度的顶点称为悬挂点(pendantnode)图的基本知识：度正则图所有顶点的度均相同的图称为正则图(regulargraph)，按照顶点的度数k称作k-正则图Kn是n-1正则图K5图的基本知识：子图G1=V1,E1,G2=V2,E2子图subgraph、真子图V1V2,E1E2，称G1是G2子图如果G1≠G2，则G1是G2真子图图的基本知识：子图生成子图spanningsubgraph如果G1是G2的子图，且V1=V2G1,G2互为补图V1=V2,E1∩E2=,V1,E1∪E2是完全图图的基本知识图的同构isomorphic|V1|=|V2|,|E1|=|E2|如果可以将V1中所有的结点一一对应地置换为V2中的结点名后得到的图等于G2图的基本知识不同构的图：化学中的同分异构体分子式相同而结构和性质不同的化合物之间互称同分异构体。分子式相同意味着V1=V2,|E1|=E2|乙醇：C2H5OH甲醚：CH3OCH3路径与回路顶点v1到vl的拟路径pseudopathv1,e1,v2,e2,v3,…,vl-1,el-1,vl其中ei=vi,vi+1或者{vi,vi+1}拟路径中的边数目称作拟路径的长度a,1,e,7,b,3,c,3,b,2,ac,4,e,4,c,3,b,7,e,4,cabcde1234567b路径与回路如果拟路径中的边各不相同，称作路径walka,1,e,7,b,3,c,4,e,6,d如果路径中的顶点各不相同，称作通路patha,1,e,7,b,3,c,5,dv1=vl的路径称为闭路径closedwalka,2,b,7,e,4,c,5,d,6,e,1,av1=vl的通路称作回路circuita,1,e,6,d,5,c,3,b,2,aabcde1234567b路径与回路路径和通路定理在有n个顶点的图G中，如果有顶点u到v的拟路径，那么u到v必有路径，并且必有长度不大于n-1的通路考虑拟路径中重复顶点的压缩闭路径和回路定理在有n个顶点的图G中，如果有顶点v到v的闭路径，那么必定有一条从v到v的长度不大于n的回路图的连通性u可达v(accessible)u=v，或者存在一条u到v的路径连通的无向图connected无向图中任意两个顶点都是可达的强连通的有向图有向图中任意两个顶点都是互相可达的图的连通性单向连通的有向图任意两个顶点，至少从一个顶点到另一个是可达的弱连通的有向图将有向图看作无向图时是连通的图的连通性连通分支（connectedcomponent）图G的连通子图G’，而且G’不是任何其它连通子图的真子图（最大性）欧拉图及欧拉路径欧拉图Eulergraph如果图G上有一条经过所有顶点、所有边的闭路径（允许顶点重复）欧拉路径Eulerwalk如果图G上有一条经过所有顶点、所有边的路径（允许顶点重复）欧拉图及欧拉路径欧拉图无向图：G连通，所有顶点的度都是偶数有向图：G弱连通，每个顶点的出度与入度相等欧拉路径无向图：G连通，恰有两个顶点的度是奇数有向图：G连通，恰有两个顶点出度与入度不相等，其中一个出度比入度多1，另一个入度比出度多1欧拉图及欧拉路径欧拉图和“一笔画”问题哥尼斯堡七桥问题哈密顿图及哈密顿通路哈密顿图Hamiltongraph如果图G上有一条经过所有顶点的回路（不要求经过所有边）也称作哈密顿回路哈密顿通路Hamiltonpath如果图G上有一条经过所有顶点的通路（非回路）哈密顿图及哈密顿通路判定定理（充分非必要）如果具有n个顶点的图G的每一对顶点的度数之和都不小于n-1，那么G中有一条哈密顿通路如果G的每一对顶点度数之和不小于n，且n=3，则G为一哈密顿图哈密顿通路问题在上个世纪七十年代被证明是“NP完全的”，NP完全问题被认为不能找到多项式时间算法（算法时间随顶点个数呈指数增长）实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。哈密顿图及哈密顿通路计算方式的进化：DNA计算1994年11月美国科学家阿德勒曼在《科学》上公布了DNA计算机理论，并成功的运用DNA计算机解决了一个有向哈密尔顿路径问题以DNA碱基序列作为信息编码的载体，利用现代分子生物学技术，在试管内控制酶作用下的DNA序列反应，作为实现运算的过程；这样，以反应前DNA序列作为输入的数据，反应后的DNA序列作为运算的结果。理论上DNA计算机具有和电子计算机同等的计算能力，但是其分子水平上的运算性能却是电子计算机所望尘莫及的哈密顿图及哈密顿通路●计算方式的进化：DNA计算DNA计算机几天的运算量就相当于计算机问世以来所有计算机的计算总量1立方分米的DNA溶液可以存储的数据超过目前所有计算机的存储容量能量消耗却只是普通计算机的几十亿分之一关于课程教材[O158/75]计算机科学中的离散结构王元元,张桂芸编著，机械工业出版社2004[O158/60]离散数学导论王元元,张桂芸编著，科学出版社2002[O158/36]离散数学王元元,李尚奋编著，科学出版社1994END特殊符号表∴,∵,╞═╡,╞═,∈,≠,∑,↓,∪,∩,╞,┠PCαΑ,βΒ,γΓ,δΔ,εΕ,ζΖ,ηΗ,θΘ,ιΙ,κΚ,λΛ,μΜ,νΝ,ξΞ,οΟ,πΠ,ρΡ,ς΢,σΣ,τΤ,υΥ,φΦ,χΧ,ψΨ,ωΩ{¬,∧,∨,→,↔}≦≧≠≤ø