一个具有n个顶点的有向图(无重边和自环)最多有( )条边。
A. n×(n-1)/2 B. n×(n-1) C. n×(n+1)/2 D. n2
代入值算:假设n=1,则排除CD,假设n=2,则最多有2条边排除A,选B
显然为完全图
n个顶点分别指向其余n-1个顶点
A n2
admin 回复 Trevor: 注意审题,有向图
victor_yan 回复 admin: 想请教下指向自己的不用算吗
admin 回复 victor_yan: 如果对于每个点都计算了指向其他点的边,那么指向自己的也是从其他点来的,所以已经被计算进去了。
B
简单图是没有平行边且没有...
用户登录可进行刷题及查看答案
简单图是没有平行边且没有自环的图
平行边:对无向图,关联一对顶点的无向边如果多于1条,则称这些边为平行边;对有向图,关联一对顶点的有向边如果多于1条,并且这些边的始点与终点相同(也就是它们的的方向相同),称这些边为平行边
自环(Loop)是一条顶点与自身连接的边。
没有平行边且没有自环,但是两个顶点可以你指向我,我指向你
所以最多的情况就是这个图中任意两个顶点两两相连,且都是互相指向
登录后提交答案