问题标题：
【计算机基础-离散数学问题求证:简单图G和其补图至少有一个为连通图】
问题描述：
计算机基础-离散数学问题
求证:简单图G和其补图至少有一个为连通图
杜佩芝回答：
如果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在补图中连通.
点击显示
数学推荐
热门数学推荐