计算机基础-离散数学问题求证:简单图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在补图中连通.

看了计算机基础-离散数学问题求证...的网友还看了以下：

关于机械式数字计算机,急1.世界上第一台机械式数字计算机是由谁花了几年时间发明的?2.谁研究出的何种　2020-03-31 …

计算机存储容量的基本单位是字节,用b表示,计算中一般用KB(千字节)或MB(兆字节)或计算机存储容　2020-05-17 …

计算机网络的基本特征不包括A.建立计算机网络主要是为了计算机资源共享B.计算机网络中用户分　2020-05-23 …

英语翻译计算机电路计算机基础计算机微机原理计算机数学基础计算机英语大学英语计算机组成与维护计算机网　2020-06-07 …

网络基础题一、填空题1．在20世纪50年代,（）和（）技术的互相结合,为计算机网络的产生奠定了理论　2020-06-25 …

计算机基础.具体指出各个选项的错误并改正.下列叙述正确的是A世界上第一台电子计算机ENIAC首次实　2020-07-02 …

计算机基础知识题：设有一段文本的机内码为C5F5D0B45043CAC7D6B8问这段文本中含有多　2020-07-09 …

一道有关网络的计算机基础题在由许多网络互连而成的庞大的计算机网络中，为了实现计算机的相互通信，必须为　2020-12-05 …

计算机基础理论试题1一、单选题1．通常人们所说的一个完整的计算机系统应包括A．运算器计算机基础理论试　2020-12-13 …

某商店有两种进价不同基计算机器,都卖64元,其中一个盈利60%,另亏本20%,这个买卖中,这家商店是　2020-12-15 …

相关搜索：计算机基础-离散数学问题求证简单图G和其补图至少有一个为连通图