优质解答
如果G不连通,则其补图必连通,下面给出证明:
设u,v是G中任意两个点,(1)如果u,v在G中不连通,即边(u,v)不在G中,由补图定义可知,(u,v)必在G的补图中,即u,v在补图中连通.(2)如果u,v在G中连通,u,v必在G的同一个连通分图中,因为G不连通,故G至少有两个连通分图,在另一个连通分图中任取一点w,则(u,w),(w,v)均不在G中,由补图定义可知(u,w),(w,v)均在G的补图中,故u-w-v是连结u,w的一条路(在补图中),故u,v在补图中连通.
如果G不连通,则其补图必连通,下面给出证明:
设u,v是G中任意两个点,(1)如果u,v在G中不连通,即边(u,v)不在G中,由补图定义可知,(u,v)必在G的补图中,即u,v在补图中连通.(2)如果u,v在G中连通,u,v必在G的同一个连通分图中,因为G不连通,故G至少有两个连通分图,在另一个连通分图中任取一点w,则(u,w),(w,v)均不在G中,由补图定义可知(u,w),(w,v)均在G的补图中,故u-w-v是连结u,w的一条路(在补图中),故u,v在补图中连通.