一条回路,它经过图中每条边一次且仅一次,称此图为欧拉图。汉密尔顿图:图中有通过每个结点恰好一次的回路。(具有汉密尔顿回路)的图.称之为汉密尔顿图。树:一个连通无回路的无向图T,称之为树。根树:如果一棵有向树,恰有一个结点的入度为0,其余所有结点的入度均为1,则称此树为根树.m叉树:在根树中,如果每个结点的出度最大是m,则称此树是m叉树.完全m叉树:在根树中,如果每个结点的出度都是m或者等于0,则称此树是完全m叉树.2.给定图的集合G={A,B,C,D,E,F,H,K,M,N,R,S,T,V,W,X,Y},其中各个图如下所示,请指出这些图中哪些是彼此同构的。2.解:同构的有:AR;BD;CMSW;EFTY;H;KX;VN。3.请画出五个具有五个结点的无向图,使之分别满足:(1)此图既是欧拉图也是汉密尔顿图。(2)此图是欧拉图但不是汉密尔顿图。(3)此图是汉密尔顿图但不是欧拉图。(4)此图是完全图K5。(5)此图是棵树解:(1)(2)(3)(4)(5)十四.有三个小题1.指出下面各个图中哪些是彼此同构的.abcdfghie解:a、h、i同构;b、d同构;c、g同构;e、f同构。2.完全二叉树中,设边数为e,叶结点数为t,求证e=2(t-1)。解:由完全m叉树公式(m-1)i=t-1这里m=2,得(2-1)i=t-1,∴i=t-1,∴T中总的结点数v为:v=i+t=(t-1)+t=2t-1,于是T的边数e:e=v-1=2t-1-1=2t-2=2(t-1)3.根据给定一组权值:1,6,2,5,3,4,1,6,2画出一棵最优完全二叉树。要求有画图的过程。解权值排序并画图:1,1,2,2,3,4,5,6,62,2,2,3,4,5,6,62,3,4,4,5,6,64,4,5,5,6,65,5,6,6,86,6,8,108,10,1212,1830321121851030841224665
全文预览
