0
$\begingroup$

Given an undirected graph $G$ with non-negative edge weights, how can we prove that the predecessor subgraph $G_{p}$ of $G$ is always connected?

Here's how the predecessor subgraph is defined: for a graph $G = (V, E)$ with source $s$, the predecessor subgraph of $G$ is $G_{p} = (V_{p}, E_{p})$, where $V_{p} = \{ v \in V : v.p \neq NIL\} \cup \{s\}$ and $E_{p} = \{ (v.p, v) : v \in V_{p} - \{s\}\}$

I've read that the predecessor subgraph forms a tree, but in the context of that claim, it was assumed the predecessor subgraph is connected and $|E_{p}| = |V_{p}| - 1$.

Can anyone offer a proof that the predecessor subgraph $G_{p}$ of a graph $G$ is always connected (or disprove the claim)?

Improve this question
$\endgroup$
5
  • $\begingroup$ I'm assuming that you're dealing with undirected graphs with non-negative edge weights, and you are interested in the predecessors from a single source vertex. Is this correct? $\endgroup$
    – Steven
    Sep 21 at 18:05
  • $\begingroup$ Also there are multiple ways to define the predecessor subgraph. Do you want a graph in which you add exactly one edge $(p,v)$ for each non-source vertex $v$ such that $p$ is the predecessor of $v$, or you want to have an edge for each possible predecessor? Are the edges undirected or directed towards $v$? If the edges are directed, what do you mean by "connected"? $\endgroup$
    – Steven
    Sep 21 at 18:17
  • $\begingroup$ In response to your first question: yes, that's correct. For the second, I've updated the question and added the definition of the predecessor subgraph I'm using $\endgroup$
    – Hugh Mann
    Sep 21 at 19:04
  • 1
    $\begingroup$ $v.p$ is not defined, but I guess it's the parent of $v$ as set by the breadth first search algorithm. $\endgroup$
    – Steven
    Sep 21 at 19:32
  • $\begingroup$ Yes, that's correct $\endgroup$
    – Hugh Mann
    Sep 21 at 19:36

1 Answer 1

Reset to default
1
$\begingroup$

Let $s$ be your source vertex and let $d(v)$ denote the distance from $s$ to $v$. Let $v_1, \dots, v_n$ be the vertices of your graph in non-decreasing order of distances from $s$.

You can show by induction on $i$ that the subgraph $G_i$ of $G_p$ induced by $\{v_1, \dots v_i\}$ is connected.

The base case is trivial as $G_1$ contains only $v_1=s$.

Consider now $i>1$. It suffices to argue that $G_i$ contains an edge $(v_j, v_i)$ for some $j<i$. By definition, the predecessor $p(v_i)$ of a vertex $v_i$ (w.r.t. the source $s$) ensures that there is a shortest path from $s$ to $v_i$ that first goes from $s$ to $p(v_i)$ and then traverses the edge $(p(v_i),v)$. Since edge-weights are non-negative, $d(p(v_i)) < d(v_i)$ which shows that $p(v)=v_j$ for some $j<i$.

Since your graph has exactly $n-1$ edges and it is connected, it is actually a tree.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you explain why it suffices to argue that $G_i$ contains an edge $(v_j, v_i)$ for some $j<i$? $\endgroup$
    – Hugh Mann
    Sep 25 at 21:22
  • 1
    $\begingroup$ By induction hypothesis the subgraph $G_{i-1}$ induced by $v_1, v_2, \dots, v_{i-1}$ is connected. If there is an edge from any of these vertices $v_j$ to $v_i$ then $G_i$ is connected too. A path from $v_h$ (with $h < i$) to $v_i$ in $G_i$ can be obtained by concatenating a path from $v_h$ to $v_j$ in $G_{i-1}$ (which is connected) with the edge $(v_j, v_i$). A path from $v_i$ to $v_h$ in $G_i$ can be obtained by concatenating the path consisting of the sole edge $(v_i, v_j)$ with a path from $v_j$ to $v_h$ in $G_{i-1}$ (which is connected). $\endgroup$
    – Steven
    Sep 25 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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