图论大神看过来~若一个平面图中,点的个数为p,边的个数为q,将此图分成一个图与他的补图,边的个数分别为q1,q2,请问下面的公式怎么来的q1+q2=0.5(p-1)*p

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/24 00:54:31
图论大神看过来~若一个平面图中,点的个数为p,边的个数为q,将此图分成一个图与他的补图,边的个数分别为q1,q2,请问下面的公式怎么来的q1+q2=0.5(p-1)*p图论大神看过来~若一个平面图中,

图论大神看过来~若一个平面图中,点的个数为p,边的个数为q,将此图分成一个图与他的补图,边的个数分别为q1,q2,请问下面的公式怎么来的q1+q2=0.5(p-1)*p
图论大神看过来~
若一个平面图中,点的个数为p,边的个数为q,将此图分成一个图与他的补图,边的个数分别为q1,q2,请问下面的公式怎么来的
q1+q2=0.5(p-1)*p

图论大神看过来~若一个平面图中,点的个数为p,边的个数为q,将此图分成一个图与他的补图,边的个数分别为q1,q2,请问下面的公式怎么来的q1+q2=0.5(p-1)*p
一个图的边集,和它的补图的边集,两者的并集是完全图的边集,而完全图中边的个数是0.5(p-1)*p,当然有q1+q2=0.5(p-1)*p
这和是否是平面图无关.另外,从你的表述中就可以看出来,不清楚什么叫补图,“将此图分成一个图与他的补图”这种说法根本不成立.
所谓一个图的补图,这是一个与原图完全不同的图,但两者的顶点集合都相同.如果原图中某两点间存在边,那么补图的这两个点之间就不存在边;反之亦然.
所以说,根本不是把原图分成某个补图,原图和补图根本是两个不同的图(但他们的边集合互补)