y*s
2 楼
你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
人太懒了是不行的。
而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
人太懒了是不行的。
w*g
3 楼
how about just depth first search from type2 nodes.
it seems type1, type2 nodes are the two sets of nodes in a bipartite graph.
I don't see any advantage of knowing this somehow.
【在 y***s 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
it seems type1, type2 nodes are the two sets of nodes in a bipartite graph.
I don't see any advantage of knowing this somehow.
【在 y***s 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
w*g
4 楼
Maybe you could search for problems related to graph coloring. I am not sure.
b*h
5 楼
Maybe Manet doesn't know much about graph theory but I guess it's not good
bashing people like that without giving some suggestions or references. I
guess Manet just needs some keyword to google or some good and easy graph
theory book to read.
I'll recommend "The Algorithm Design Manual" by Steven S. Skiena. My
experience is it's very easy to read and covers common problems with real
implementation. The book also has a CDROM with full book text. Check the book
in your library and copy the whole
【在 y***s 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
bashing people like that without giving some suggestions or references. I
guess Manet just needs some keyword to google or some good and easy graph
theory book to read.
I'll recommend "The Algorithm Design Manual" by Steven S. Skiena. My
experience is it's very easy to read and covers common problems with real
implementation. The book also has a CDROM with full book text. Check the book
in your library and copy the whole
【在 y***s 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
r*h
6 楼
I may not fully understand this problem.
But if nodes of type 1 are just pick up UNIFORMLY from [1, a] nodes, and if
you want a closed form of A/B/a, I think the result should be like "with prob.
***, and a = ***, it is connected..." Right?
But if nodes of type 1 are just pick up UNIFORMLY from [1, a] nodes, and if
you want a closed form of A/B/a, I think the result should be like "with prob.
***, and a = ***, it is connected..." Right?
r*h
7 楼
I guess the certainty may depend only on the total degree of each part only.
(Just a guess, not sure). Then the problem seems to be a pure probability
problem, which requires to decide how to distribute these degress in the nodes
of type one...
By finding the total degree. I am not sure, but I guess you may try on small
A/B, and find some rules. Besides, it seems to only depend on A/B, not a
in this part?
(Just a guess, not sure). Then the problem seems to be a pure probability
problem, which requires to decide how to distribute these degress in the nodes
of type one...
By finding the total degree. I am not sure, but I guess you may try on small
A/B, and find some rules. Besides, it seems to only depend on A/B, not a
in this part?
s*m
8 楼
我大概知道一点图论知识，可是我还是不会计算这个概率
【在 y***s 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
【在 y***s 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
m*r
9 楼
It looks like a probability problem, not much graph theory needed.
if
threshold,
if
threshold,
r*n
10 楼
I don't think there is a solution on your problem. Your a is only a upper
bound of the selection for all type 1 nodes. You can always build a connected
graph and a non-connected graph for any a. So you can't judge the connectivity
just based on your a.
not
【在 m*****r 的大作中提到】
: It looks like a probability problem, not much graph theory needed.
:
: if
: threshold,
bound of the selection for all type 1 nodes. You can always build a connected
graph and a non-connected graph for any a. So you can't judge the connectivity
just based on your a.
not
【在 m*****r 的大作中提到】
: It looks like a probability problem, not much graph theory needed.
:
: if
: threshold,
y*u
11 楼
Yes, this should be a very difficult problem.
Just consider a much easier case where we put an edge between each pair
of vertices with probability p, and ask if the graph is connected. People
have shown that there exists some threshold for p, if p is below the
threshold, the graph is almost certainly disconnected; if p is above
the threshold, the graph is almost certainly connected. This is called
the phase transition phenomena. More interestingly, many other monotone
properties besides conn
【在 s*m 的大作中提到】
: 我大概知道一点图论知识，可是我还是不会计算这个概率
s*m
12 楼
那就模拟好了 :)
【在 y***u 的大作中提到】
:
: Yes, this should be a very difficult problem.
: Just consider a much easier case where we put an edge between each pair
: of vertices with probability p, and ask if the graph is connected. People
: have shown that there exists some threshold for p, if p is below the
: threshold, the graph is almost certainly disconnected; if p is above
: the threshold, the graph is almost certainly connected. This is called
: the phase transition phenomena. More interestingly, many other monotone
: properties besides conn
【在 y***u 的大作中提到】
:
: Yes, this should be a very difficult problem.
: Just consider a much easier case where we put an edge between each pair
: of vertices with probability p, and ask if the graph is connected. People
: have shown that there exists some threshold for p, if p is below the
: threshold, the graph is almost certainly disconnected; if p is above
: the threshold, the graph is almost certainly connected. This is called
: the phase transition phenomena. More interestingly, many other monotone
: properties besides conn
y*u
13 楼
对啊，transition很sharp，应该很快就知道个大概了.
【在 s*m 的大作中提到】
: 那就模拟好了 :)
【在 s*m 的大作中提到】
: 那就模拟好了 :)
相关阅读
SERP'11麻烦推荐基本算法书呗？vapnik牛x的那个叫VC theory半道出家的和科班出身的差别到底有多大?信用分数知多少？creditreport提供免费查询信用分数请问给对方发邮件 (转载)P != NP 被证出来了，同学们Where is the Computer science 版? (转载)听说master的ad要一个月内答复?Anyone going to ICML?PhD找程序员工作的时候publication有人看吗？Matlab开多线程真爽啊 (转载)半路出家CS应该上如下一些初级课程么？MobiCom vs. CCS该不该读cs master有人对powerPC 汇编熟悉吗，问个弱智问题面向CS的湾区智能电网和能效职业讨论会问个 google scholar citation 的问题 (转载)请教做Computer Vision, Medical Imaging工作请问VB在NYC附近的就业前景 (转载)