图论大神看过来~若一个平面图中,点的个数为p,边的个数为q,将此图分成一个图与他的补图,边的个数分别为q1,q2,请问下

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

质本洁 幼苗

共回答了21个问题采纳率:100% 举报

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

1年前

8
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.020 s. - webmaster@yulucn.com