图论第一次作业.doc

.习题一：l 4. 证明下面两图同构。证明:作映射f : vi ui (i=1,2.10) 容易证明，对vi v j E (a),有f (v i vj,),=,ui,uj,E,(b) (1 i 10, 1j 10 ) 由图的同构定义知，图(a)与(b)是同构的。l 5.证明：四个顶点的非同构简单图有11个。证明：设四个顶点中边的个数为m，则有：m=0:m=1 ：m=2：m=3：m=4：m=5：m=6：因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。l 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,