The Gateway to Computer Science Excellence
+1 vote
149 views
Let K$_n$ be such that the vertices are labeled 1,2,3,...n.

The number of simple paths between v$_1$ and v$_n$ such that the labels on the path are strictly increasing ____________________
in Graph Theory by Active (4.8k points)
edited by | 149 views
0
B ) ??
0
Yes, B is answer.

Can you please explain me.
0

I don't know the correct method for this but if you have time in exam you can guess (hit and trial) like this--

0
what does the statement mean "such that labels on the path are strictly increasing" ?
0
I think it is like 12,3,5,7,9....n.(many sequences possible).

Strictly increasing means we can't take one vertex more than once..like 1,1,2,3.... It is not allowed
0

Gupta731  see the answer 

0
i added the answer... you may check it.

1 Answer

+4 votes
Best answer

Note that given is Complete graph ===> there is a edge between every pair of vertices.

we have n vertices, let name them as V1,V2,...Vn.

We want the paths between V1 and Vn.

there are remaining, n-2 elements, i.e., V2,V3,....Vn-1 . ===> let the Set S = { remaining elements } ===> |S| = n-2.

what is the Power Set of this elements ===> size of power Set of S = 2n-2.

in the power set, each set is lead to unique path ( labels are in the path are strictly increasing order ) between V1 and Vn.

∴ No.of Simple paths between V1 and Vn Such that the labels in the path are strictly increasing order = 2n-2.

 

ex:-

let take K5..... name the labels as V1,V2,V3,V4,V5.

We want the simple paths between V1 and V5.

remaining vertices are {V2,V3,V4}, then the power set is contains the following set

1) ∅ ====> the path which we required is V1 --- V5.

2) { V2 } ====> the path which we required is V1 --- V2 --- V5.

3) { V3 } ====> the path which we required is V1 --- V3 --- V5.

4) { V4 } ====> the path which we required is V1  --- V4 --- V5.

5) { V2,V3 } ====> the path which we required is V1 --- V2 --- V3 --- V5.

6) { V2,V4 } ====> the path which we required is V1 --- V2 --- V4 --- V5.

7) { V3,V4 } ====> the path which we required is V1  --- V3 --- V4 --- V5.

8) { V2,V3,V4 } ====> the path which we required is V1 --- V2 --- V3 --- V4 --- V5.



Now i am interested in that,what the formula if in the question the restriction " labels are in the path are strictly increasing order " removed ?

the power set contains = 2n-2. sets

we can partition them as

$\binom{n-2}{0} + \binom{n-2}{1} + \binom{n-2}{2} + ...+ \binom{n-2}{n-2}$ = 2n-2.

$\binom{n-2}{0}$ ===> lead to 1 permutation paths

$\binom{n-2}{1}$ ===> lead to 1 permutation paths

$\binom{n-2}{2}$ ===> lead to 2 permutation paths

............

$\binom{n-2}{n-2}$ ===> lead to (n-2)! permutation paths

∴ No.of Simple paths between V1 and Vn  = $\binom{n-2}{0} * 1! + \binom{n-2}{1} * 1! + \binom{n-2}{2} * 2! + ...+ \binom{n-2}{n-2} * (n-2)! $.

by Veteran (65.8k points)
selected by
0
yeah great !

thanks
0
Yes, now its proper.

i will make a note of it. Thank you

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,737 questions
57,385 answers
198,557 comments
105,369 users