请教图论面试题# JobHunting - 待字闺中
i*a
1 楼
前两天面试被难住了，特来这里求教。
有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
能用一次的前提下，最多能取得多少个三角形。
有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
能用一次的前提下，最多能取得多少个三角形。
l*b
2 楼
N/3?
i*a
3 楼
应该不是，如果用N=6来试的话，可以取出4个三角形
【在 l*******b 的大作中提到】
: N/3?
【在 l*******b 的大作中提到】
: N/3?
f*4
4 楼
新增的结点可与所有孤边分别组成三角形，因此
F(n+1)=C(n,2)-3*F(n)+F(n)
求拍~
【在 i*a 的大作中提到】
: 前两天面试被难住了，特来这里求教。
: 有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
: 能用一次的前提下，最多能取得多少个三角形。
F(n+1)=C(n,2)-3*F(n)+F(n)
求拍~
【在 i*a 的大作中提到】
: 前两天面试被难住了，特来这里求教。
: 有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
: 能用一次的前提下，最多能取得多少个三角形。
i*a
5 楼
F(5) = 2
F(6) = 4
貌似不对。。。
【在 f*******4 的大作中提到】
: 新增的结点可与所有孤边分别组成三角形，因此
: F(n+1)=C(n,2)-3*F(n)+F(n)
: 求拍~
F(6) = 4
貌似不对。。。
【在 f*******4 的大作中提到】
: 新增的结点可与所有孤边分别组成三角形，因此
: F(n+1)=C(n,2)-3*F(n)+F(n)
: 求拍~
l*b
6 楼
花眼了，数边，N(N-1)/6
N=6可以有5个，很好造的
【在 i*a 的大作中提到】
: 应该不是，如果用N=6来试的话，可以取出4个三角形
N=6可以有5个，很好造的
【在 i*a 的大作中提到】
: 应该不是，如果用N=6来试的话，可以取出4个三角形
f*e
7 楼
这么难的题会是面试题？除非你是面数学系的组合数学方向faculty职位。
http://mathoverflow.net/questions/81414/how-many-edge-disjoint-
【在 i*a 的大作中提到】
: 前两天面试被难住了，特来这里求教。
: 有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
: 能用一次的前提下，最多能取得多少个三角形。
http://mathoverflow.net/questions/81414/how-many-edge-disjoint-
【在 i*a 的大作中提到】
: 前两天面试被难住了，特来这里求教。
: 有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
: 能用一次的前提下，最多能取得多少个三角形。
i*a
8 楼
每条连线都只能用一次，N=6如何得到的F(6)=5？
我的结果是：
123
234
456
136
能给出你的结果吗？
【在 l*******b 的大作中提到】
: 花眼了，数边，N(N-1)/6
: N=6可以有5个，很好造的
我的结果是：
123
234
456
136
能给出你的结果吗？
【在 l*******b 的大作中提到】
: 花眼了，数边，N(N-1)/6
: N=6可以有5个，很好造的
i*a
9 楼
多谢指点，职位不是faculty，不过对数学要求十分高。
【在 f*****e 的大作中提到】
: 这么难的题会是面试题？除非你是面数学系的组合数学方向faculty职位。
: http://mathoverflow.net/questions/81414/how-many-edge-disjoint-
【在 f*****e 的大作中提到】
: 这么难的题会是面试题？除非你是面数学系的组合数学方向faculty职位。
: http://mathoverflow.net/questions/81414/how-many-edge-disjoint-
f*e
10 楼
非常接近正确答案了
a*3
11 楼
N-2，感觉像是convex hull的trangulation问题
l*b
12 楼
6个点，两两连成线，三条线一个三角形，点不一定是顶点呀
5组边：
16 25 34
15 64 23
14 35 26
13 24 56
12 36 45
【在 i*a 的大作中提到】
: 每条连线都只能用一次，N=6如何得到的F(6)=5？
: 我的结果是：
: 123
: 234
: 456
: 136
: 能给出你的结果吗？
5组边：
16 25 34
15 64 23
14 35 26
13 24 56
12 36 45
【在 i*a 的大作中提到】
: 每条连线都只能用一次，N=6如何得到的F(6)=5？
: 我的结果是：
: 123
: 234
: 456
: 136
: 能给出你的结果吗？
i*a
13 楼
可以大概说一下答案吗？现在暂时不能下载文章。
【在 f*****e 的大作中提到】
: 非常接近正确答案了
【在 f*****e 的大作中提到】
: 非常接近正确答案了
i*a
14 楼
问题的前提是每三个点连成三角形，不是三条线就组成三角形，所以必须是闭合的。
【在 l*******b 的大作中提到】
: 6个点，两两连成线，三条线一个三角形，点不一定是顶点呀
: 5组边：
: 16 25 34
: 15 64 23
: 14 35 26
: 13 24 56
: 12 36 45
【在 l*******b 的大作中提到】
: 6个点，两两连成线，三条线一个三角形，点不一定是顶点呀
: 5组边：
: 16 25 34
: 15 64 23
: 14 35 26
: 13 24 56
: 12 36 45
f*e
15 楼
https://www.dropbox.com/s/w56r7w38768k7l8/triangles_in_Kn.pdf
【在 i*a 的大作中提到】
: 可以大概说一下答案吗？现在暂时不能下载文章。
【在 i*a 的大作中提到】
: 可以大概说一下答案吗？现在暂时不能下载文章。
i*a
16 楼
多谢！
【在 f*****e 的大作中提到】
: https://www.dropbox.com/s/w56r7w38768k7l8/triangles_in_Kn.pdf
【在 f*****e 的大作中提到】
: https://www.dropbox.com/s/w56r7w38768k7l8/triangles_in_Kn.pdf
q*m
17 楼
N/ 3 ?
【在 i*a 的大作中提到】
: 前两天面试被难住了，特来这里求教。
: 有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
: 能用一次的前提下，最多能取得多少个三角形。
【在 i*a 的大作中提到】
: 前两天面试被难住了，特来这里求教。
: 有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
: 能用一次的前提下，最多能取得多少个三角形。
q*m
18 楼
123
234
那么 23不是用了两次吗？
【在 i*a 的大作中提到】
: 每条连线都只能用一次，N=6如何得到的F(6)=5？
: 我的结果是：
: 123
: 234
: 456
: 136
: 能给出你的结果吗？
234
那么 23不是用了两次吗？
【在 i*a 的大作中提到】
: 每条连线都只能用一次，N=6如何得到的F(6)=5？
: 我的结果是：
: 123
: 234
: 456
: 136
: 能给出你的结果吗？
i*a
19 楼
好眼力
123
345
561
246
楼上已经有大侠给出答案了。问题本身挺难的。
[发表自未名空间手机版 - m.mitbbs.com]
【在 q****m 的大作中提到】
: 123
: 234
: 那么 23不是用了两次吗？
123
345
561
246
楼上已经有大侠给出答案了。问题本身挺难的。
[发表自未名空间手机版 - m.mitbbs.com]
【在 q****m 的大作中提到】
: 123
: 234
: 那么 23不是用了两次吗？
s*V
20 楼
很简单，两两连线N(N-1)/2,每条边只能用一次，所以是N(N-1)/6.
【在 i*a 的大作中提到】
: 前两天面试被难住了，特来这里求教。
: 有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
: 能用一次的前提下，最多能取得多少个三角形。
【在 i*a 的大作中提到】
: 前两天面试被难住了，特来这里求教。
: 有N个点，两两之间都能连成直线，每三个点能连成一个三角形。问在每两点间连线只
: 能用一次的前提下，最多能取得多少个三角形。
s*n
21 楼
每三个点能连成一个三角形
这个已经保证了 ?
不需要检查三点成形的条件?
【在 s*****V 的大作中提到】
: 很简单，两两连线N(N-1)/2,每条边只能用一次，所以是N(N-1)/6.
e*o
22 楼
I don't think it is true.
let N = 4, N(N-1)/6 = 2; however, the answer is 1.
【在 s*****V 的大作中提到】
: 很简单，两两连线N(N-1)/2,每条边只能用一次，所以是N(N-1)/6.
let N = 4, N(N-1)/6 = 2; however, the answer is 1.
【在 s*****V 的大作中提到】
: 很简单，两两连线N(N-1)/2,每条边只能用一次，所以是N(N-1)/6.
l*b
23 楼
接近N(N-1)/6,但不总是,前面的大虾给了paper,证明还绕了几个弯弯.相等的例子是这个
http://en.wikipedia.org/wiki/Steiner_system
http://en.wikipedia.org/wiki/Steiner_system
s*V
24 楼
还有三条边都连着同一点这种情况没有考虑。如果这种情形很稀少，就接近于 N(N-1)/
6。
【在 e******o 的大作中提到】
: I don't think it is true.
: let N = 4, N(N-1)/6 = 2; however, the answer is 1.
6。
【在 e******o 的大作中提到】
: I don't think it is true.
: let N = 4, N(N-1)/6 = 2; however, the answer is 1.
相关阅读
是否答应三哥同事的refer请求分享一个e-verify的名单吧关于回绝offer的问题感觉CS full time机会比intern多多了OPT等待太煎熬问道open end的题退PhD，申OPT的复杂情况，非常头疼【面试秘籍】《Acing the Interview请问有人找过career coach/career counselor么？OPT 1年之后还有grace period吗？为什么很多招实习的广告里都有这么一句话？估计死在这一题上了。OPT volunteer 问题求助看见国内招工广告就生气！换工作中一般多久通知现雇主发一个MSFT bing的onsite面经Job Openning一个Java Technical Suppport Engineer Opening, 加州湾区over next three weeks是什么意思？心碎,很有希望拿到offer,却刚发现今年H1B指标没了, 我该怎么办?