Find a recurrence to count paths in a directed graph

Wyvern666 11/16/2018 at 18:19. 1 answers, 0 views
combinatorics discrete-mathematics graph-theory recurrence-relations computer-science

Suppose we have an unweighted directed graph with vertices numbered as $1...n$

From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$.

My task is to find a recurrence $f(i,j)$ to compute the number of paths from vertex $i$ to vertex $j$.

My current toughs:

For a base case, if $i \geq j$ then $f(i,j)=0$. For example, there is no path from $1$ to $1$, or from $2$ to $2$. And there is no path from $2$ to $1$.

For a general case, and when $i < j$, from $i$ there are edges to $i+1$, $i+2$ and $i+7$. So we can reach $j$ from $j-1$, $j-2$ and $j-7$. I think the recurrence depends on $f(j-1,j)$, $f(j-2,j)$ and $f(j-7,j)$.

Im doing well?, really i don''t find this intuitive at all.

1 Answers


Brian M. Scott 08/14/2015.

You’re on the right track.

Suppose that $i<j$. Each path from $i$ to $j$ must end with an edge from one of the vertices $j-7,j-2,j-1$ to $j$. Let $k$ be one of these vertices; there are $f(i,k)$ paths from $i$ to $k$, each of which extends to a path from $i$ to $j$ whose last edge is $\{k,j\}$. Thus, you can almost set

$$f(i,j)=f(i,j-7)+f(i,j-2)+f(i,j-1)\;.\tag{1}$$

There are a couple of potential problems here. First, one or more of $k\in\{j-7,j-2,j-1\}$ may be less than $i$. That’s not really a problem, since in that case we set $f(i,k)=0$, as you already did. Next, $j-7$, for instance, might be less than $1$. We can solve that by agreeing that $f(i,j)=0$ if $i$ or $j$ is out of the range from $1$ through $n$.

The last problem is what to do if one of the numbers $j-7,j-2,j-1$ equals $i$. In order for $(1)$ to give the right answer, we must have $f(i,i)=0$, as you have it in your question. However, this isn’t actually correct: there is one path from $i$ to $i$, of length $0$.

One way around this difficulty is to set $f(i,i)=1$ for $i=1,\ldots,n$ as an initial condition and then modify $(1)$ to read

$$f(i,j)=f(i,j-7)+f(i,j-2)+f(i,j-1)-\big[i\in\{j-7,j-2,j-1\}\big]\;,$$

where the last term is an Iverson bracket.

There are other ways to make the necessary adjustment, but the irregularity of the set $\{1,2,7\}$ makes all of them a bit messy.


HighResolutionMusic.com - Download Hi-Res Songs

1 (G)I-DLE

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
2 The Chainsmokers

Beach House flac

The Chainsmokers. 2018. Writer: Andrew Taggart.
3 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
4 Nicki Minaj

No Candle No Light flac

Nicki Minaj. 2018. Writer: Denisia “Blu June” Andrews;Kathryn Ostenberg;Brittany "Chi" Coney;Brian Lee;TJ Routon;Tushar Apte;ZAYN;Nicki Minaj.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
7 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
8 BTS

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
9 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
10 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
11 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
12 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.
13 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
14 Anne-Marie

Rewrite The Stars flac

Anne-Marie. 2018. Writer: Benj Pasek;Justin Paul.
15 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
16 Imagine Dragons

Machine flac

Imagine Dragons. 2018. Writer: Wayne Sermon;Daniel Platzman;Dan Reynolds;Ben McKee;Alex Da Kid.
17 Little Mix

The Cure flac

Little Mix. 2018.
18 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
19 Rita Ora

Velvet Rope flac

Rita Ora. 2018.
20 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.

Related questions

Hot questions

Language

Popular Tags