The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
276 views

Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly coming in and exactly one edge going out. We allow self-loops. How many graphs have exactly two cycles ?

  1. $\sum_{k=1}^{n-1} k!(n-k)!$
  2. $\frac{n!}{2}\bigg[\sum_{k=1}^{n-1} \frac{1}{k(n-k)}\bigg]$
  3. $n!\bigg[\sum_{k=1}^{n-1} \frac{1}{k}\bigg]$
  4. $\frac{n!(n-1)}{2}$
  5. None of the above
in Graph Theory by Veteran (420k points)
edited by | 276 views

1 Answer

+5 votes
Best answer

We need to find from $\{1,2,\ldots,n\}$ vertices how many graphs exist which are having exactly two cycles when self loops are allowed.

When $n=1$ there is no such graph with two cycles.

0 graph.

When $n=2$

1 graph exists.

When $n=3$

3 graphs exist.

When $n=4$

11 graphs exist.

For $n=4$

(A) $\sum_{k=1}^{n-1}k!(n-k)! = 16$

(B) $\frac{n!}{2}[\sum_{k=1}^{n-1}\frac{1}{k(n-k)}] = 11$

(C) $n![\sum_{k=1}^{n-1}\frac{1}{k}] = 44$

(D) $\frac{n!(n-1)}{2} = 36$

Option B is answer.

by Loyal (9k points)
edited by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,362 questions
55,788 answers
192,413 comments
90,933 users