补充资料：图的嵌入

图的嵌入


圈的嵌入【脚户如n加苗吨;印呻ay~八Ka】 把一个图的所有顶点和边分别映射到一个给定空间的点和连续曲线的一个映射，使得一条边所关联的顶点映射成对应曲线的端点一个平则岑水(正孚血r如同山吧)是一个嵌人，它使得相异点对应于相异顶点，而对应于边的曲线不通过对应于顶点的点(除了边的端点之外)，而且不相交.任一图可以正则嵌人到3维空间内.一个图可以正则嵌人到一个平面内就称为可于率甲·存在非可平面图，例如图凡和凡，3(见可平面图(g旧ph，planar)，图1).一个图G可以正则嵌人的2维定向曲面的最小亏格称为G的亏格(g泊璐)下(G).特别地，已证明 1(。一3、(n一4)「 下(凡)=l二=一洲洽二一}， J 12L’式中凡是具有n个顶点的完全图，且Ja【是不小于a的最小整数; 1(m一2)(。一2、f 下(凡二)=l二二竺一一二乙乙玉竺二一二兰二!， J 4L’式中凡，，是完全二部图(见二部图(g旧ph，bipar-tite)).下(Q。)=l+(n一4)·2月一3，式中Q。是陀维立方体一个图G的厚摩(1场比众溺)0(G)是当G表示为可平面子图的并图时这些可平面子图的最小个数G.特别地，已证明 _，。、_「尸+71，_二。，。_ 8(凡)=卜二告二卜若p笋9，10; 以、一，’L6」’一r 0(凡)，8(凡。)=3; In+z[ 0(Q。)=厂一.二1; 以\“”’」4L’ 1 mn「 0(入..)二I二二es一二-一一-二丁! “‘一、”’」2(m+”一2)L(可能有一些例外情形).与图的嵌人有关的其他数值特征也已曾研究过.这些数值特征包括:交叉数(n切叮比rof cllx洛咧罗)—一个图嵌人到一个给定曲面时，它的边相交的最小次数;糙度(。oa招ene粥)—一给定图的无公共边的非可平面子图的最大个数等.非定向曲面上的嵌人也曾研究过.一个图到一个”维整点格的嵌人是到这种格的一个映射，它使得顶点映射为相异格点，而边映射为格边. 图到曲面上与格上的嵌入问题，在自动计算机设计、通讯设计等领域出现.【补注】对于这里所讨论的参数的新近综述，见【AI]和【A2].有关的两篇重要文献是fA3】和【A4].

说明：补充资料仅用于学习参考，请勿用于其它任何用途。