algorithm - Number of cycles in a random graph -

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