离散数学(四)

离散数学第四部分图论引言图论是离散数学的重要组成部分，是近代应用数学的重要分支。人们常称1736年是图论历史元年，因为在这一年瑞士数学家欧拉（Euler）发表了图论的首篇论文——《哥尼斯堡七桥问题无解》，所以人们普遍认为欧拉是图论的创始人。1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著《有限图与无限图理论》，这是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。近40年来，随着计算机科学的发展，图论更以惊人的速度向前发展，有人形容说：真是异军突起，活跃非凡。其主要原因有二：其一，计算机科学的发展为图论的发展提供了计算工具；其二，现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系，从而推动科学技术不断地攀登新的高峰。作为描述事务之间关系的手段或称工具，目前，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。例1：Konisberg七桥问题能不能一次走遍所有的七座桥，而每座桥只准经过一次？例2：聚会问题任意6人聚会中，必有3人彼此相识，或有3人彼此不相识用两种颜色填涂完全图K6的各边，必包含有同色的“三角形”K3例3：INSTANTINSANITYWeconcludethissectionbylookingatapuzzlewhichhasbeenpopularrecently,andwhichhasbeenmarketedunderthenameof‘InstantInsanity’.Itconcernsfourcubeswhosefacesarecoloredred,blue,greenandyellowinsuchawaythateachcubecontainsatleastonefaceofeachcolor;theproblemistopilethesecubesupontopofeachotherinsuchawaythateachofthefour4×1sidesoftheresultingsquareprismshowsafaceofeachcolor.INSTANTINSANITYInordertosolvethisproblem,werepresenteachcubebyagraphonfourvertices,onevertexcorrespondingtoeachcolor;ineachsuchgraph,twoverticesareadjacentifandonlyifthecubeinquestionhasthecorrespondingtothecubesofFig.onleftareshowninFig.onnext.INSTANTINSANITYWeshallfinditconvenienttosuperimposethesegraphstoformanewgraph(Fig.onnext)..INSTANTINSANITYRBGY231424413132INSTANTINSANITYFront&backLeft&rightSinceeverysolutionofthepuzzlehastwofacesofeachcoloroneachofthetwopairsofoppositesidesofthe4×1prism,itisnotdifficulttoseethattherequiredsolutionisobtainedbyfindingtwoedge-disjointsub-graphswhichcontainexactlyoneedgeofeachnumberandwhichcontainonlyverticesofdegreetwo.Thenrepresentthecolorsappearingonthefront-and-backandontheleft-and-rightsidesofthe4×1prism;thesolutioncannowbereadofffromthesesub-graphs.例4：旋转鼓问题一个编码盘分成16个相等的扇面，每个扇面由绝缘体或导体组成，表示0和1两种状态，其中a,b,c,d四个位置的扇面组成一组二进制输出，如图所示。试问这16个二进制的序列应如何排列，才能恰好组成0000到1111的16组四位二进制输出，同时旋转一周后又返回到0000状态。旋转鼓问题图论解法000001100010101011110111E1=0001E3=0011E7=0111E14=1110E12-1100E8=1000E9=1001E2=0010E4=0100E6=0110E11=1011E13=1101E5=0101E10=1010E0=0000E15=1111Dijkstra最短路同构树（TREE)