algorithm - Number of cycles in a random graph -
in undirected random graph of 8 vertices, probability of border beingness nowadays between pair of vertices in 1/2. expected number of unordered cycles of length 3?
here's how thought of going it:
method 1 cycles ("unordered" assuming mean vertices can taken in order) of length 3 triangles.
letting number of vertices = v, , no of such cycles beingness c
for n=3, c = 1
for n = 4, c = 4. (a square 2 diagonal lines. 4 unique triangles). ....
for n>3, c(n) = (n-2) + (n-2)(n-3) + (n-4), generalizing.
this because: allow start outside edge, , triangles possible base. first border take (2 vertices gone there), there (n-2) other vertices take 3rd point of triangle. (n-2) in first term.
next, lastly term because lastly side take base of operations our triangles on have leftmost , rightmost triangles taken first side chose , immediate predecessor.
the middle term product of remaining number of edges , possible triangles.
.--------. . . . . . .
with above set of 8 vertices 1 can trivially think out visually. (if improve diagrams needed, shall needful!). v=8, c(8) = 40. so, probability of border 1/2 . . .
method 2 number of triangles n points nc3, c "combination". half of these edges not expected exist . . .
i not sure how proceed beyond point. hints in right direction great. btw not homework question.
you have nc3 possible triangles. triangle appear 3 edges must exist - probability of specific triangle appear 1/8.
the expected number of triangles (nc3) / 8
.
in case, 8c3 / 8
or 7.
algorithm graph-algorithm
No comments:
Post a Comment