,恰有一个结点的入度为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. 指出下面各个图中哪些是彼此同构的.РaРbРcРdРfРgРhРiРeР解: 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,6Р2,2,2,3,4,5,6,6Р2,3,4,4,5,6,6Р4,4,5,5,6,6Р5, 5,6,6,8Р6,6,8,10Р8,10,12Р12,18Р30Р3Р2Р1Р1Р2Р18Р5Р10Р30Р8Р4Р12Р2Р4Р6Р6Р5
全文预览
