图论第6章课件.ppt

* * * * * * * * * 下面是Windows2000?Professional中的一个著名漏洞。在Windows?2000启动之后，按下Ctrl+Alt+Del进行登录，在登录界面出现后将光标移至用户名输入框，按键盘上的Ctrl+Shift键进行输入法切换，在出现“全拼”时调出输入法的帮助菜单，继续选择“输入法入门”，点击“选项按钮”，从这里你就可以完全避开操作系统的登录验证，访问到计算机的物理硬盘，然后可以创建帐户。这就是著名的Windows2000输入法漏洞。网络安全中有许多都是这类简单的问题导致的，只要公司稍加注意，就可以大大提高公司网络的安全性。 ????虽然解决这个问题的方法很简单，只要到微软的网站去下载Service?Pack2.0进行安装即可。但是，如果公司没有懂得网络安全的工程师，谁又会想到去下载这个补钉呢？所以，培养足够数量的网络安全人才成为当务之急！ * * * * * 对H1的一个平面嵌入 及H1的任意桥B，考察 是否为空。 若存在H1的桥B，使 ，则由定理22， 不是G容许的，这表明G是不可平面图； 否则取H1的桥B1，令H2 = H1∪B1，再取一个面 ,将B1画入 f，可得到相应的 。 将H2作为新的H1重复上面过程，如此继续可得G的一个可平面子图序列 H1, H2,…,以及相应的平面嵌入 满足 若G是可平面图，则序列 必终止于G的一个平面嵌入 。 例3 用定理22按上一段描述的过程 判断右图所示的图G的可平面性。 a b c 解 取图中红边所构成的圈作为H1。有三座桥，即边a自身，b自身和c自身构成的三个子图。此时有 a b c 取桥a，令H2= H1∪a，再取一个a在 中可画入的面，可得相应的 ，如右图的红边所示。 此时，对H2的桥b和c均有 取桥b。 b c c 令H3= H2∪b，再取b在 中唯一的 可画入的面，即 的外部面，将b画入该面中可得 ，如右图中红边所示。此时，对H3的桥c，因 故判断G是不可平面图。 二、平面性算法 注：对图的可平面性的判断，只需考察简单块。这是因一个图G的可平面性与其基础简单图相同。且简单图G是可平面图当且仅当G的每个块是可平面图。 平面性算法 设G是至少三个顶点的简单块。 1. 取G的一个圈H1，求出H1的一个平面嵌入 。置i=1。 2. 若 ，则停（此时 为G的一个平面嵌入）；否则，确定G中Hi的所有桥，并对每一座桥B，求出集合 。 3. 若存在一座桥B，使 ，则停（此时由定理22，G为不可平面图）；否则，在Hi的所有桥中确定一个使 最小的B，并取 。 4. 在桥B中取一条连接 Hi 上两个附着顶点的路， ，置Hi+1=Hi∪Pi，并把 Pi 画在 的面 f 内，得到 Hi+1的一个平面嵌入 。 5. 令 i = i+1， 转2。 例4 用平面性算法判断下图G的平面性。 1 6 5 4 3 2 9 8 7 解 （1）取圈H1=2315642，其中平面嵌入如下图。H1的桥，分别用边集表示于图之下（下同）。 2 4 6 5 1 3 B1={14}, B2={17, 47, 76} B3={28, 38, 89, 96, 95} 1 6 5 4 3 2 9 8 7 G-E(H1) 2 4 6 5 1 3 B1={14}, B2={17, 47, 76} B3={28, 38, 89, 96, 95} （2）对每个Bi， 均含有两个Bi可画入的面------圈 的内部面和外部面。 1 6 5 4 3 2 9 8 7 G-E(H1) 2 4 6 5 1 3 B4={17, 47, 76} B5={28, 38, 89, 96, 95} （3） 取B1及 的内部面作为f。 B1中连接H1上两个附着顶点的路P1仅一条，即P1=41。 置H2= H1∪P1，并将P1画入 f 内得 如图: （4）对每个Bi， 其