《设g1和g2是两个简单无向图》由会员分享，可在线阅读，更多相关《设g1和g2是两个简单无向图（2页珍藏版）》请在金锄头文库上搜索。
1、设G1 和G2 是两个简单无向图，G1的节点集合V1=v1，v2，vn，G2的节点集合V2=w1，w2，wn，若对于任意i=1，2，n，均有G1-viG2-wi，则G1G2证明：原命题等价于求证如果G1G2 不成立，那么总存在i使得G1-viG2-wi 不成立。反证法：假设G1G2 不成立，有G1-viG2-wi 成立。（i=1，2，n）如果不能在G1 中找到某个节点，使得在G1 中去掉该节点后与在G2 中去掉相应节点后同构。那么此时即为对于任意的i=1，2，n都不成立，那么与假设矛盾，所以假设不成立，此种情况下原命题得证。如果如果能在G1 中找到某个节点，使得在G1 中去掉该节点后与在G2
2、中去掉相应节点后同构。那么记G1 中所有符合条件的点中的任意一个为v1，记G2 中所有符合条件的点中的任意一个为w1 ，那么此时有G1-v1G2-w1。此种情况下继续进行下一步。如果不能在G1 中找到某个节点vkv1，使得在G1 中去掉该节点后与在G2 中去掉相应节点wkw1后同构。那么此时即为对于任意的i=2，n都不成立，那么与假设矛盾，所以假设不成立，此种情况下原命题得证。如果如果能在G1 中找到某个节点vkv1，使得在G1 中去掉该节点后与在G2 中去掉相应节点wkw1后同构。那么记G1 中所有符合条件的点中的任意一个为v2，记G2 中所有符合条件的点中的任意一个为w2，那么此时有G1-
3、v2G2-w2。此种情况下继续进行下一步。一直重复上述步骤，如果能做到第n-1步：（n-1）如果不能在G1 中找到某个节点vkv1，v2，vn-2，使得在G1 中去掉该节点后与在G2 中去掉相应节点wkw1，w2，wn-2后同构。那么此时即为对于任意的i=n-1，n都不成立，那么与假设矛盾，所以假设不成立，此种情况下原命题得证。如果如果能在G1 中找到某个节点vkv1，v2，vn-2，使得在G1 中去掉该节点后与在G2 中去掉相应节点wkw1，w2，wn-2后同构。那么记G1 中所有符合条件的点中的任意一个为vn-1，记G2 中所有符合条件的点中的任意一个为wn-1，那么此时有G1-vn-1G
4、2-wn-1。此种情况下继续进行下一步。(n)如果两图都去点最后一个节点后不同构，那么此时与假设矛盾，所以假设不成立，此种情况下原命题得证。反证法：假设同时去点最后一个节点vn和wn后，还是有G1-vnG2-wn 。即：两个图前n-1个结点构成的图同构，由于G1 与G2 不同构，所以两个图中最后一个点与其余点的连接方式一定不同（如果相同，那么显然两图同构）。如果vn 与其余所有点一共有x条连线，wn 与其余所有点一共有y条连线，显然xy0（若为哦，则两图同构）。1、 如果xy,那么不妨设xy，假设vn 与vp (其中1pn，这样的p有x个且pN*)相连。wn 与wq (其中1qn，这样的q有y个且qN*)相连。如果存在p=q=j。那么此时与第j步骤矛盾。若不存在p=q，那么此时对于任意的q=r,与第r步骤矛盾。所以此种情况下，与前面步骤矛盾，所以假设不成立，得证。2、 如果x=y，假设vn 与vp (其中1pn，这样的p有x个且pN*)相连。wn 与wq (其中1qn，这样的q有x个且qN*)相连那么不可能存在pq（此时同构），在任意的p=tq时与前面的第t步骤矛盾，所以假设不成立。综上所述，在所有情况下假设皆与事实矛盾，所以原命题得证。
