r*******e
发帖数: 7583 | 1 给n个节点，用有向的边把它们连起来
问最多可以连多少条边而不形成环
a<=>b这种情况也算是环，所以不能出现 |
c******a
发帖数: 789 | |
g**e
发帖数: 6127 | 3 显然不是
【在 c******a 的大作中提到】
: 画来画去都是n－1
|
r**h
发帖数: 1288 | 4 无向边是N-1
有向边应该是N(N-1)/2？
给每个节点赋一个不同的rank，然后每个节点对于所有rank小于自己的节点都建立一条
有向边 |
r*******e
发帖数: 7583 | 5 有向的边，环的定义是能顺着箭头回到原点
a->b
a->c
b->c
没有环
【在 c******a 的大作中提到】
: 画来画去都是n－1
|
c******a
发帖数: 789 | 6 哦，原来是有向图，那就一定不是n－1了，我继续画画！
【在 g**e 的大作中提到】
: 显然不是
|
z****e
发帖数: 54598 | |
c******a
发帖数: 789 | |
c******a
发帖数: 789 | 9 我觉得是
(n-1)+(n-2)+...+1
【在 z****e 的大作中提到】
: sum(1+...+n-1)
|
r*******e
发帖数: 7583 | 10 对头
怎么证明n(n-1)/2是最大值呢？
【在 r**h 的大作中提到】
: 无向边是N-1
: 有向边应该是N(N-1)/2？
: 给每个节点赋一个不同的rank，然后每个节点对于所有rank小于自己的节点都建立一条
: 有向边
|
|
|
z****e
发帖数: 54598 | 11 对，我之前想成组合了
看了原题，原来是问sum
已经改了
【在 c******a 的大作中提到】
: 我觉得是
: (n-1)+(n-2)+...+1
|
z****e
发帖数: 54598 | 12 sum(1+...+n-1)
= (n-1)/2*(1+n-1)
=n*(n-1)/2
【在 r*******e 的大作中提到】
: 对头
: 怎么证明n(n-1)/2是最大值呢？
|
r**h
发帖数: 1288 | 13 因为在此基础上任意再加一条边都会产生环啊
【在 r*******e 的大作中提到】
: 对头
: 怎么证明n(n-1)/2是最大值呢？
|
c******a
发帖数: 789 | 14 a<=>b不行的话，最多也就画n(n-1)/2条edge吧。要证明的部分是：那么多条也不会形
成cycle
【在 r*******e 的大作中提到】
: 对头
: 怎么证明n(n-1)/2是最大值呢？
|
r*********n
发帖数: 4553 | |
z****e
发帖数: 54598 | 16 可以再多，但是再多就形成环了
你楼上说得正确
【在 c******a 的大作中提到】
: a<=>b不行的话，最多也就画n(n-1)/2条edge吧。要证明的部分是：那么多条也不会形
: 成cycle
|
c******a
发帖数: 789 | 17 不会证明。
不过可以用bfs来想，从第一个node开始，“发射”完之后就去掉，这样就不会有cycle。
这么发射着，最后就是n(n-1)/2条edge |
c******a
发帖数: 789 | 18 4node就已经不对了。。。我也往那想过
【在 r*********n 的大作中提到】
: 这是排列组合题吧
: n choose 2？
|
r*********n
发帖数: 4553 | 19 好像是topological sort一样，箭头只能往一个方向走，比如从左到右，你画一画，就
好像是手动counting (n choose 2)一样
如果在多一个，就必定是一个从右到左的箭头，形成cycle
【在 r*******e 的大作中提到】
: 对头
: 怎么证明n(n-1)/2是最大值呢？
|
r*********n
发帖数: 4553 | 20 LZ不是说了答案是n(n-1)/2嘛？
【在 c******a 的大作中提到】
: 4node就已经不对了。。。我也往那想过
|
|
|
r*******e
发帖数: 7583 | 21 是的。我觉得严格来说要分两步回答
首先用topological的方法，可以得到一个解n(n-1)/2
其次，任何别的方法，连出来也只能最多n(n-1)/2
【在 r**h 的大作中提到】
: 因为在此基础上任意再加一条边都会产生环啊
|
t****d
发帖数: 423 | 22 F(n)=F(n-1)+(n-1)
★ 发自iPhone App: ChineseWeb 7.8
【在 r*******e 的大作中提到】
: 给n个节点，用有向的边把它们连起来
: 问最多可以连多少条边而不形成环
: a<=>b这种情况也算是环，所以不能出现
|
b***e
发帖数: 1419 | 23 这个不是显然么：
存在性的就是全序集即可。
n(n-1)/2已经是完全图了（无向的话），再加一个必然有a<=>b发生.
【在 r*******e 的大作中提到】
: 是的。我觉得严格来说要分两步回答
: 首先用topological的方法，可以得到一个解n(n-1)/2
: 其次，任何别的方法，连出来也只能最多n(n-1)/2
|
z****e
发帖数: 54598 | 24 全序集英语怎么说？
【在 b***e 的大作中提到】
: 这个不是显然么：
: 存在性的就是全序集即可。
: n(n-1)/2已经是完全图了（无向的话），再加一个必然有a<=>b发生.
|
b***e
发帖数: 1419 | |
f**********2
发帖数: 2401 | 26 有向图的话是，N(N-1)/2吧
#1: 对于出发的节点1，可以产生N-1个边，而不产生环；
#2：对于出发的节点2，只有N-2个边（因为不可以再连接2->1），而不产生环。
。。。
#n:对于节点N出发的边，只有0.因为和之前任何一个N-1中的节点连接，势必产生环。
Sum=0+1+...+(N-1)=N(N-1)/2 |
t****a
发帖数: 1212 | 27 首先，构造f(n)=n(n-1)/2结果的方法可以用递推产生：
f(1)=0
f(2)=1
..
f(n+1)=f(n)+n # 第n+1个点指向点1..n，所以加入n条边且不会产生环
其次，n(n-1)/2最大的原因是再加任何一条边进去都会形成a<=>b
【在 r*******e 的大作中提到】
: 是的。我觉得严格来说要分两步回答
: 首先用topological的方法，可以得到一个解n(n-1)/2
: 其次，任何别的方法，连出来也只能最多n(n-1)/2
|
x*****0
发帖数: 452 | |
