Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a directed unweighted cyclic graph G consisting of up to 30 nodes and 30 edges find number of paths between i,j for all i,j in G

If there are infinite number of paths detect it

Example

In this example the matrix would be:

    A B C D

A  0 1 0 1

B  0 0 0 1

C  0 1 0 2

D  0 0 0 0

What's an algorithm that can find such matrix? (else DP)

share|improve this question
    
Can there be infinite number of paths when your graph has at most 30 nodes and 30 edges? –  epsilon Apr 13 '13 at 21:13
    
@epsilon: if there's a circuit, maybe? –  ronash Apr 13 '13 at 21:16
1  
@ronash: Yes but "A path is a trail in which all vertices (except perhaps the first and last ones) are distinct" Am I wrong? –  epsilon Apr 13 '13 at 21:21
    
but the problem stated that the vertices don't have to be distinct. –  mohammed essam Apr 14 '13 at 15:54

1 Answer 1

up vote 4 down vote accepted

Conveniently enough, I've something in my thesis on this. Let $A$ be the adjacency matrix that you describe. I'll just completely transcribe what seems relevant here:


We say a path with origin $x_0$ and extremity $x_r$, which we denote $x_0,x_1,\ldots,x_r$ is without backtracking if $x_{i+1}\neq x_{i-1}$ for all $i\in\{1,\ldots,r-1\}$. We define a series of matrices $A_r$ where $$ (A_r)_{xy}=\#\text{ of paths of length $r$ without backtracking with origin $x$ and extremity $y$}. $$

Given that $A_0=\text{Id}$ and $A_1=A$, the following allows us to recursively define $A_r$.

(i) $A_2=A_1^2-k\cdot\text{Id}.$

(ii) For $r\geq 2$, $A_{r+1}=A_rA_1-(k-1)\,A_{r-1}$.

PROOF:

(i) Let $x,y\in V$. Then $(A_1^2)_{xy}$ is the number of all paths of length 2 between $x$ and $y$. If $x\neq y$, we cannot have backtracking, thus $(A_1^2)_{xy}=(A_2)_{xy}$. If $x=y$, then the only way for a path of length 2 between $x$ and itself is along of the exactly $k$ edges connected to $x$, and is therefore found through backtracking. Thus we must subtract $k\cdot\text{Id}$ to eliminate these choices, and thus $A_2=A_1^2-k\cdot\text{Id}$ as required.

(ii) As above, let $x,y\in V$. Then $(A_rA_1)_{xy}$ is the number of paths of length $r+1$ between $x$ and $y$ without backtracking, except possibly at the last step. Let $x=x_0,\ldots,x_{r-1},x_r,x_{r+1}=y$ be such a path. If $x_{r-1}\neq y$, then there cannot be backtracking and so $(A_{r+1})_{xy}=(A_rA_1)_{xy}$. However if $x_{r-1}=y$, then we have backtracking at the last step. There are $(k-1)(A_{r-1})_{xy}$ such paths and they must be deleted. This completes the proof.


This insight is courtesy of Lemma 1.4.1 in Elementary Number Theory, Group Theory, and Ramanujan Graphs by Davidoff, Sarnak, and Valette. Hopefully this can give you some insight into your algorithm. I should warn that my situation called for directed graphs, which made the adjacency matrix symmetric. I believe this is stated in enough generality that there aren't insurmountable difficulties in applying this in your case.

share|improve this answer
    
can you please explain more, as i am new to graph theory –  mohammed essam Apr 14 '13 at 15:57
    
Could you be specific about what you need explained? –  Ian Coley Apr 14 '13 at 16:32
    
the term extremity and the symbols –  mohammed essam Apr 14 '13 at 17:04
    
Extremity is just the end of the path, in your case $[j]$. Which of the symbols here? It's usual matrix notation otherwise. –  Ian Coley Apr 14 '13 at 17:05
    
i mean the matrix notations –  mohammed essam Apr 14 '13 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.