s***e
发帖数: 1490 | |
y***s
发帖数: 294 | 2 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
人太懒了是不行的。 |
w*******g
发帖数: 9932 | 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 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
|
w*******g
发帖数: 9932 | 4
Maybe you could search for problems related to graph coloring. I am not sure. |
b*********h
发帖数: 1 | 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 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
|
r******h
发帖数: 809 | 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? |
r******h
发帖数: 809 | 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? |
s*m
发帖数: 34 | 8 我大概知道一点图论知识，可是我还是不会计算这个概率
【在 y***s 的大作中提到】
: 你只需要一点点最最起码的图论基本知识就足够回答这个问题了。
: 而像你现在这样一点点最最起码的基本知识都没有，别人就算给你讲都没法讲。
: 人太懒了是不行的。
|
m*****r
发帖数: 9 | 9 It looks like a probability problem, not much graph theory needed.
if
threshold, |
r*******n
发帖数: 51 | 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,
|
y***u
发帖数: 101 | 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
发帖数: 34 | 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
发帖数: 101 | 13 对啊，transition很sharp，应该很快就知道个大概了.
【在 s*m 的大作中提到】
: 那就模拟好了 :)
|
