Mixing
A given arboresescence is a shortest path tree if and only if $ d_B(r,v) leq d_B(r,u) + l(u,v)$
$begingroup$
Definition Let $D = (V, A)$ be a directed graph, with $r in V$. Suppose that a directed path from $r$ to $v$
exists, for every $v in V setminus {r}$. An r-arborescence in D is by definition a set of arcs $B subseteq A$ such
that $(V, B)$ has a unique directed $r -v$ walk, for every $v in V setminus {r}$.
Suppose a length function l : $A to mathbb R $ has been given with the graph $D$.
We also know that no directed circuits
of negative length exist in D. Now, a shortest path tree (SP tree) rooted at $r$ for $(D, l)$ is an
r-arborescence $B$ such that the unique $r–v$ path in $(V, B)$ is a shortest path (with respect
to l) in D.
Show that a given r-arborescence B is an SP tree if and only if, for every $(u, v) in A$,
$$d_B(r, v) leq d_B(r, u) + l(u, v)$$
where $d_B(x, y)$ denotes the distance in the graph (V, B) with respect to the length function
$l$ restricted to $B subseteq A$.
My approach: $(implies)$
We know that if we have an $SP$ tree rooted at $r$, we know that there is a shortest path from $r$ to $v$, because this is a shortest path tree, denote the distance $d_B(r,v)$. If we take any other point $u$ adjacent to $v$ on the shortest path tree we know that the $r-u$ path is also of minimal length. If we are at $u$ we still need to go from $u$ to $v$ now by some arc, this is given by the length function $l(u,v)$, in total we have travelled $d(r,u)+l(u,v)$. We are not certain this way of reaching $v$ will give us a path of minimal distance, but we know lengths are positive, so adding it will give us an inequality:
$$ d_B(r,v) leq d_B(r,u) + l(u,v)$$
$(impliedby)$
Now I am not sure how this inequality implies that $B$ is a shortest path tree.
I was thinking of negating the statement and generating some counterexample of the form:
Suppose we have a tree that is not a shortest path tree, then there exists an arc $(u,v)$ such that:
$$d_B(r,v) > d_B(r,u) +l(u,v) $$
discrete-mathematics graph-theory trees
asked Jan 9 at 15:20
Wesley StrikWesley Strik
1,858423
$endgroup$
add a comment |
$begingroup$
Definition Let $D = (V, A)$ be a directed graph, with $r in V$. Suppose that a directed path from $r$ to $v$
exists, for every $v in V setminus {r}$. An r-arborescence in D is by definition a set of arcs $B subseteq A$ such
that $(V, B)$ has a unique directed $r -v$ walk, for every $v in V setminus {r}$.
Suppose a length function l : $A to mathbb R $ has been given with the graph $D$.
We also know that no directed circuits
of negative length exist in D. Now, a shortest path tree (SP tree) rooted at $r$ for $(D, l)$ is an
r-arborescence $B$ such that the unique $r–v$ path in $(V, B)$ is a shortest path (with respect
to l) in D.
Show that a given r-arborescence B is an SP tree if and only if, for every $(u, v) in A$,
$$d_B(r, v) leq d_B(r, u) + l(u, v)$$
where $d_B(x, y)$ denotes the distance in the graph (V, B) with respect to the length function
$l$ restricted to $B subseteq A$.
My approach: $(implies)$
We know that if we have an $SP$ tree rooted at $r$, we know that there is a shortest path from $r$ to $v$, because this is a shortest path tree, denote the distance $d_B(r,v)$. If we take any other point $u$ adjacent to $v$ on the shortest path tree we know that the $r-u$ path is also of minimal length. If we are at $u$ we still need to go from $u$ to $v$ now by some arc, this is given by the length function $l(u,v)$, in total we have travelled $d(r,u)+l(u,v)$. We are not certain this way of reaching $v$ will give us a path of minimal distance, but we know lengths are positive, so adding it will give us an inequality:
$$ d_B(r,v) leq d_B(r,u) + l(u,v)$$
$(impliedby)$
Now I am not sure how this inequality implies that $B$ is a shortest path tree.
I was thinking of negating the statement and generating some counterexample of the form:
Suppose we have a tree that is not a shortest path tree, then there exists an arc $(u,v)$ such that:
$$d_B(r,v) > d_B(r,u) +l(u,v) $$
discrete-mathematics graph-theory trees
asked Jan 9 at 15:20
Wesley StrikWesley Strik
1,858423
$endgroup$
add a comment |
$begingroup$
Definition Let $D = (V, A)$ be a directed graph, with $r in V$. Suppose that a directed path from $r$ to $v$
exists, for every $v in V setminus {r}$. An r-arborescence in D is by definition a set of arcs $B subseteq A$ such
that $(V, B)$ has a unique directed $r -v$ walk, for every $v in V setminus {r}$.
Suppose a length function l : $A to mathbb R $ has been given with the graph $D$.
We also know that no directed circuits
of negative length exist in D. Now, a shortest path tree (SP tree) rooted at $r$ for $(D, l)$ is an
r-arborescence $B$ such that the unique $r–v$ path in $(V, B)$ is a shortest path (with respect
to l) in D.
Show that a given r-arborescence B is an SP tree if and only if, for every $(u, v) in A$,
$$d_B(r, v) leq d_B(r, u) + l(u, v)$$
where $d_B(x, y)$ denotes the distance in the graph (V, B) with respect to the length function
$l$ restricted to $B subseteq A$.
My approach: $(implies)$
We know that if we have an $SP$ tree rooted at $r$, we know that there is a shortest path from $r$ to $v$, because this is a shortest path tree, denote the distance $d_B(r,v)$. If we take any other point $u$ adjacent to $v$ on the shortest path tree we know that the $r-u$ path is also of minimal length. If we are at $u$ we still need to go from $u$ to $v$ now by some arc, this is given by the length function $l(u,v)$, in total we have travelled $d(r,u)+l(u,v)$. We are not certain this way of reaching $v$ will give us a path of minimal distance, but we know lengths are positive, so adding it will give us an inequality:
$$ d_B(r,v) leq d_B(r,u) + l(u,v)$$
$(impliedby)$
Now I am not sure how this inequality implies that $B$ is a shortest path tree.
I was thinking of negating the statement and generating some counterexample of the form:
Suppose we have a tree that is not a shortest path tree, then there exists an arc $(u,v)$ such that:
$$d_B(r,v) > d_B(r,u) +l(u,v) $$
discrete-mathematics graph-theory trees
asked Jan 9 at 15:20
Wesley StrikWesley Strik
1,858423
$endgroup$
Definition Let $D = (V, A)$ be a directed graph, with $r in V$. Suppose that a directed path from $r$ to $v$
exists, for every $v in V setminus {r}$. An r-arborescence in D is by definition a set of arcs $B subseteq A$ such
that $(V, B)$ has a unique directed $r -v$ walk, for every $v in V setminus {r}$.
Suppose a length function l : $A to mathbb R $ has been given with the graph $D$.
We also know that no directed circuits
of negative length exist in D. Now, a shortest path tree (SP tree) rooted at $r$ for $(D, l)$ is an
r-arborescence $B$ such that the unique $r–v$ path in $(V, B)$ is a shortest path (with respect
to l) in D.
Show that a given r-arborescence B is an SP tree if and only if, for every $(u, v) in A$,
$$d_B(r, v) leq d_B(r, u) + l(u, v)$$
where $d_B(x, y)$ denotes the distance in the graph (V, B) with respect to the length function
$l$ restricted to $B subseteq A$.
My approach: $(implies)$
We know that if we have an $SP$ tree rooted at $r$, we know that there is a shortest path from $r$ to $v$, because this is a shortest path tree, denote the distance $d_B(r,v)$. If we take any other point $u$ adjacent to $v$ on the shortest path tree we know that the $r-u$ path is also of minimal length. If we are at $u$ we still need to go from $u$ to $v$ now by some arc, this is given by the length function $l(u,v)$, in total we have travelled $d(r,u)+l(u,v)$. We are not certain this way of reaching $v$ will give us a path of minimal distance, but we know lengths are positive, so adding it will give us an inequality:
$$ d_B(r,v) leq d_B(r,u) + l(u,v)$$
$(impliedby)$
Now I am not sure how this inequality implies that $B$ is a shortest path tree.
I was thinking of negating the statement and generating some counterexample of the form:
Suppose we have a tree that is not a shortest path tree, then there exists an arc $(u,v)$ such that:
$$d_B(r,v) > d_B(r,u) +l(u,v) $$
discrete-mathematics graph-theory trees
discrete-mathematics graph-theory trees
asked Jan 9 at 15:20
Wesley StrikWesley Strik
1,858423
asked Jan 9 at 15:20
Wesley StrikWesley Strik
1,858423
edited Jan 9 at 15:30
Wesley Strik
asked Jan 9 at 15:20
Wesley StrikWesley Strik
1,858423
asked Jan 9 at 15:20
Wesley StrikWesley Strik
1,858423
asked Jan 9 at 15:20
Wesley StrikWesley Strik
1,858423
1,858423
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint:
- Run the Bellman–Ford_algorithm over the whole graph $(V, A)$ initialized as implied by $B$ (i.e., the
distanceandpredecessorarrays calculated from $B$). - Will there be any changes done by the algorithm?
I hope this helps $ddotsmile$
answered Jan 9 at 16:14
dtldarekdtldarek
32.3k743100
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067564%2fa-given-arboresescence-is-a-shortest-path-tree-if-and-only-if-d-br-v-leq-d%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint:
- Run the Bellman–Ford_algorithm over the whole graph $(V, A)$ initialized as implied by $B$ (i.e., the
distanceandpredecessorarrays calculated from $B$). - Will there be any changes done by the algorithm?
I hope this helps $ddotsmile$
answered Jan 9 at 16:14
dtldarekdtldarek
32.3k743100
$endgroup$
add a comment |
$begingroup$
Hint:
- Run the Bellman–Ford_algorithm over the whole graph $(V, A)$ initialized as implied by $B$ (i.e., the
distanceandpredecessorarrays calculated from $B$). - Will there be any changes done by the algorithm?
I hope this helps $ddotsmile$
answered Jan 9 at 16:14
dtldarekdtldarek
32.3k743100
$endgroup$
add a comment |
$begingroup$
Hint:
- Run the Bellman–Ford_algorithm over the whole graph $(V, A)$ initialized as implied by $B$ (i.e., the
distanceandpredecessorarrays calculated from $B$). - Will there be any changes done by the algorithm?
I hope this helps $ddotsmile$
answered Jan 9 at 16:14
dtldarekdtldarek
32.3k743100
$endgroup$
Hint:
- Run the Bellman–Ford_algorithm over the whole graph $(V, A)$ initialized as implied by $B$ (i.e., the
distanceandpredecessorarrays calculated from $B$). - Will there be any changes done by the algorithm?
I hope this helps $ddotsmile$
answered Jan 9 at 16:14
dtldarekdtldarek
32.3k743100
answered Jan 9 at 16:14
dtldarekdtldarek
32.3k743100
answered Jan 9 at 16:14
dtldarekdtldarek
32.3k743100
answered Jan 9 at 16:14
dtldarekdtldarek
32.3k743100
32.3k743100
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067564%2fa-given-arboresescence-is-a-shortest-path-tree-if-and-only-if-d-br-v-leq-d%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
