Path Property of Directed Acyclic Graphsdoes this complete directed graph have this property?Graphs: First Order Characterisation Of A pathProve that if $r(x)≠r(y)$ for every 2 distinct vertices $x$ and $y$ of $D$ then $D$ contain a Hamiltonian path.Path cover in directed graphsLabelings of infinite directed acyclic graphsShortest path in a graph with weighted edges and verticesA question about a labeled directed graphTransform Node-Labeled Graph to equivalent Edge-LabeledLet $G = (V,E)$ be a tree, then $G$ is a caterpillar graph $iff$ The line graph of $G$ contains a Hamiltonian path.Does a finite, strongly-connected, labeled digraph with no non-trivial automorphism always have a unique path?
Did arcade monitors have same pixel aspect ratio as TV sets?
2.8 Why are collections grayed out? How can I open them?
What does chmod -u do?
Is it better practice to read straight from sheet music rather than memorize it?
Electoral considerations aside, what are potential benefits, for the US, of policy changes proposed by the tweet recognizing Golan annexation?
What is this cable/device?
What should you do when eye contact makes your subordinate uncomfortable?
Which one is correct as adjective “protruding” or “protruded”?
Creepy dinosaur pc game identification
Why is so much work done on numerical verification of the Riemann Hypothesis?
Delivering sarcasm
Is it improper etiquette to ask your opponent what his/her rating is before the game?
Biological Blimps: Propulsion
Problem with TransformedDistribution
What if a revenant (monster) gains fire resistance?
How do I find all files that end with a dot
If a character has darkvision, can they see through an area of nonmagical darkness filled with lightly obscuring gas?
Why did the Mercure fail?
Create all possible words using a set or letters
How much character growth crosses the line into breaking the character
What is the evidence for the "tyranny of the majority problem" in a direct democracy context?
How could a planet have erratic days?
Why should universal income be universal?
Loading commands from file
Path Property of Directed Acyclic Graphs
does this complete directed graph have this property?Graphs: First Order Characterisation Of A pathProve that if $r(x)≠r(y)$ for every 2 distinct vertices $x$ and $y$ of $D$ then $D$ contain a Hamiltonian path.Path cover in directed graphsLabelings of infinite directed acyclic graphsShortest path in a graph with weighted edges and verticesA question about a labeled directed graphTransform Node-Labeled Graph to equivalent Edge-LabeledLet $G = (V,E)$ be a tree, then $G$ is a caterpillar graph $iff$ The line graph of $G$ contains a Hamiltonian path.Does a finite, strongly-connected, labeled digraph with no non-trivial automorphism always have a unique path?
$begingroup$
Suppose we are given a directed acyclic graph $G$, and each node is assigned a label with two real numbers like in the following example. We are given a set of source vertices and a set of sink vertices. We construct a new graph where all source vertices are replaced by one vertex, all vertices reachable from the source vertices by another vertex and so forth. We then assign labels to these new vertices as follows: for the first label we take the maximum value of all the labels in that reachable set and for the second label we take the minimum value of all the lables. Like for $L_1$ we take the maximum of $(40,10)$ and the minimum of the second label that is minimum of $(8, 6)$ and thus the label of the new graph is $(40, 6)$.
I have written this formally as follows:
Let $G=(V,E)$ be a directed acyclic graph. Consider $source subset V$ to be source vertices which have no inward edges into them and $sink subset V$ to be sink vertices from which no outward edges are present. Consider $L_k = distance(source, v) = k$ , ie, $L_k$ is the set of vertices which are at a distance $k$ from the source vertices. Each vertex is labeled with two real numbers defined by the functions $a$ and $b$ $a : v rightarrow mathbbR$ and $b : v rightarrow mathbbR$, $forall v in V$.
Consider a new graph $G'=(V',E')$ where $|V'| = k$. and each vertex in this graph corresponds to a set $L_i$ of the graph $G$, ie, there is a bijective function $f:L_i rightarrow v_i$, $forall i, 1leq i leq k $. The edge set $E'$ of this graph is defined as $(v_i, v_i+1, forall i, 1 leq i leq k-1$. Thus, this new graph is a path graph. Similar to the original graph, each vertex in this graph is labeled with two real numbers defined by the functions $a' : v' rightarrow mathbbR$ and $b' : v' rightarrow mathbbR$ where $a'(v_i') = maxa(v), forall v in L_i$ and $b'(v_i') = minb(v), forall v in L_i$, $forall 1 leq i leq k$.
Is this formalism correct? Now we need to show that if there is a particular vertex in the new graph such that its first label value is $ge x$ then there is a path in the original graph also where there is a vertex whose first label is $ge x$. Like for instance in the example above, if $x$ is say $50$, then the third vertex in the new graph has the first label as $60 ge 50$. There is a path is the original graph where the first label is also $60 ge 50$. If this is not true provide a counterexample. I have again written this formally below.
Prove that if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') geq x$ then there is a path $v in G$ from source to sink such there is a vertex $v$ where $a(v) geq x$ and if in the path graph $G'$ there is a vertex $v'$ such that $b'(v') leq x$ then there is a path $v in G$ from source to sink such there is a vertex $v$ where $b(v) leq x$ or provide a counterexample. Is this formal definition correct?
Attempt : I tried to find a counterexample but could not find any. So for the proof attempt I tried arguing on the basis of the paths. For the first case, if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') geq x$, then let us label this path as $v_0, v_1, v_2...v_k$ and the first vertex where the label $a'$ of the vertex $ge x$ be $v_n$. Assume for the purpose of contradiction that such a path does not exist in the original graph $G$. This means that the first label of all paths in the original graph $G lt x$. When building the new graph $G'$ we assigned the label of the vertex as the maximum value of all the labels in $L_i$. As a result of this construction, we have built the new graph $G'$ and obtained a vertex where its first label is $geq$x. For this vertex to be present in the new graph $G'$ it would have to be present in the original graph $G$ as well otherwise it could not be present in the new graph $G'$. This contradicts our claim that that such a path does not exist in the original graph $G$.
Is this proof correct or am I missing something or am I on the wrong track here?
graph-theory directed-graphs
asked Mar 15 at 17:14
kauraykauray
19010
$endgroup$
add a comment |
$begingroup$
Suppose we are given a directed acyclic graph $G$, and each node is assigned a label with two real numbers like in the following example. We are given a set of source vertices and a set of sink vertices. We construct a new graph where all source vertices are replaced by one vertex, all vertices reachable from the source vertices by another vertex and so forth. We then assign labels to these new vertices as follows: for the first label we take the maximum value of all the labels in that reachable set and for the second label we take the minimum value of all the lables. Like for $L_1$ we take the maximum of $(40,10)$ and the minimum of the second label that is minimum of $(8, 6)$ and thus the label of the new graph is $(40, 6)$.
I have written this formally as follows:
Let $G=(V,E)$ be a directed acyclic graph. Consider $source subset V$ to be source vertices which have no inward edges into them and $sink subset V$ to be sink vertices from which no outward edges are present. Consider $L_k = distance(source, v) = k$ , ie, $L_k$ is the set of vertices which are at a distance $k$ from the source vertices. Each vertex is labeled with two real numbers defined by the functions $a$ and $b$ $a : v rightarrow mathbbR$ and $b : v rightarrow mathbbR$, $forall v in V$.
Consider a new graph $G'=(V',E')$ where $|V'| = k$. and each vertex in this graph corresponds to a set $L_i$ of the graph $G$, ie, there is a bijective function $f:L_i rightarrow v_i$, $forall i, 1leq i leq k $. The edge set $E'$ of this graph is defined as $(v_i, v_i+1, forall i, 1 leq i leq k-1$. Thus, this new graph is a path graph. Similar to the original graph, each vertex in this graph is labeled with two real numbers defined by the functions $a' : v' rightarrow mathbbR$ and $b' : v' rightarrow mathbbR$ where $a'(v_i') = maxa(v), forall v in L_i$ and $b'(v_i') = minb(v), forall v in L_i$, $forall 1 leq i leq k$.
Is this formalism correct? Now we need to show that if there is a particular vertex in the new graph such that its first label value is $ge x$ then there is a path in the original graph also where there is a vertex whose first label is $ge x$. Like for instance in the example above, if $x$ is say $50$, then the third vertex in the new graph has the first label as $60 ge 50$. There is a path is the original graph where the first label is also $60 ge 50$. If this is not true provide a counterexample. I have again written this formally below.
Prove that if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') geq x$ then there is a path $v in G$ from source to sink such there is a vertex $v$ where $a(v) geq x$ and if in the path graph $G'$ there is a vertex $v'$ such that $b'(v') leq x$ then there is a path $v in G$ from source to sink such there is a vertex $v$ where $b(v) leq x$ or provide a counterexample. Is this formal definition correct?
Attempt : I tried to find a counterexample but could not find any. So for the proof attempt I tried arguing on the basis of the paths. For the first case, if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') geq x$, then let us label this path as $v_0, v_1, v_2...v_k$ and the first vertex where the label $a'$ of the vertex $ge x$ be $v_n$. Assume for the purpose of contradiction that such a path does not exist in the original graph $G$. This means that the first label of all paths in the original graph $G lt x$. When building the new graph $G'$ we assigned the label of the vertex as the maximum value of all the labels in $L_i$. As a result of this construction, we have built the new graph $G'$ and obtained a vertex where its first label is $geq$x. For this vertex to be present in the new graph $G'$ it would have to be present in the original graph $G$ as well otherwise it could not be present in the new graph $G'$. This contradicts our claim that that such a path does not exist in the original graph $G$.
Is this proof correct or am I missing something or am I on the wrong track here?
graph-theory directed-graphs
asked Mar 15 at 17:14
kauraykauray
19010
$endgroup$
add a comment |
$begingroup$
Suppose we are given a directed acyclic graph $G$, and each node is assigned a label with two real numbers like in the following example. We are given a set of source vertices and a set of sink vertices. We construct a new graph where all source vertices are replaced by one vertex, all vertices reachable from the source vertices by another vertex and so forth. We then assign labels to these new vertices as follows: for the first label we take the maximum value of all the labels in that reachable set and for the second label we take the minimum value of all the lables. Like for $L_1$ we take the maximum of $(40,10)$ and the minimum of the second label that is minimum of $(8, 6)$ and thus the label of the new graph is $(40, 6)$.
I have written this formally as follows:
Let $G=(V,E)$ be a directed acyclic graph. Consider $source subset V$ to be source vertices which have no inward edges into them and $sink subset V$ to be sink vertices from which no outward edges are present. Consider $L_k = distance(source, v) = k$ , ie, $L_k$ is the set of vertices which are at a distance $k$ from the source vertices. Each vertex is labeled with two real numbers defined by the functions $a$ and $b$ $a : v rightarrow mathbbR$ and $b : v rightarrow mathbbR$, $forall v in V$.
Consider a new graph $G'=(V',E')$ where $|V'| = k$. and each vertex in this graph corresponds to a set $L_i$ of the graph $G$, ie, there is a bijective function $f:L_i rightarrow v_i$, $forall i, 1leq i leq k $. The edge set $E'$ of this graph is defined as $(v_i, v_i+1, forall i, 1 leq i leq k-1$. Thus, this new graph is a path graph. Similar to the original graph, each vertex in this graph is labeled with two real numbers defined by the functions $a' : v' rightarrow mathbbR$ and $b' : v' rightarrow mathbbR$ where $a'(v_i') = maxa(v), forall v in L_i$ and $b'(v_i') = minb(v), forall v in L_i$, $forall 1 leq i leq k$.
Is this formalism correct? Now we need to show that if there is a particular vertex in the new graph such that its first label value is $ge x$ then there is a path in the original graph also where there is a vertex whose first label is $ge x$. Like for instance in the example above, if $x$ is say $50$, then the third vertex in the new graph has the first label as $60 ge 50$. There is a path is the original graph where the first label is also $60 ge 50$. If this is not true provide a counterexample. I have again written this formally below.
Prove that if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') geq x$ then there is a path $v in G$ from source to sink such there is a vertex $v$ where $a(v) geq x$ and if in the path graph $G'$ there is a vertex $v'$ such that $b'(v') leq x$ then there is a path $v in G$ from source to sink such there is a vertex $v$ where $b(v) leq x$ or provide a counterexample. Is this formal definition correct?
Attempt : I tried to find a counterexample but could not find any. So for the proof attempt I tried arguing on the basis of the paths. For the first case, if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') geq x$, then let us label this path as $v_0, v_1, v_2...v_k$ and the first vertex where the label $a'$ of the vertex $ge x$ be $v_n$. Assume for the purpose of contradiction that such a path does not exist in the original graph $G$. This means that the first label of all paths in the original graph $G lt x$. When building the new graph $G'$ we assigned the label of the vertex as the maximum value of all the labels in $L_i$. As a result of this construction, we have built the new graph $G'$ and obtained a vertex where its first label is $geq$x. For this vertex to be present in the new graph $G'$ it would have to be present in the original graph $G$ as well otherwise it could not be present in the new graph $G'$. This contradicts our claim that that such a path does not exist in the original graph $G$.
Is this proof correct or am I missing something or am I on the wrong track here?
graph-theory directed-graphs
asked Mar 15 at 17:14
kauraykauray
19010
$endgroup$
Suppose we are given a directed acyclic graph $G$, and each node is assigned a label with two real numbers like in the following example. We are given a set of source vertices and a set of sink vertices. We construct a new graph where all source vertices are replaced by one vertex, all vertices reachable from the source vertices by another vertex and so forth. We then assign labels to these new vertices as follows: for the first label we take the maximum value of all the labels in that reachable set and for the second label we take the minimum value of all the lables. Like for $L_1$ we take the maximum of $(40,10)$ and the minimum of the second label that is minimum of $(8, 6)$ and thus the label of the new graph is $(40, 6)$.
I have written this formally as follows:
Let $G=(V,E)$ be a directed acyclic graph. Consider $source subset V$ to be source vertices which have no inward edges into them and $sink subset V$ to be sink vertices from which no outward edges are present. Consider $L_k = distance(source, v) = k$ , ie, $L_k$ is the set of vertices which are at a distance $k$ from the source vertices. Each vertex is labeled with two real numbers defined by the functions $a$ and $b$ $a : v rightarrow mathbbR$ and $b : v rightarrow mathbbR$, $forall v in V$.
Consider a new graph $G'=(V',E')$ where $|V'| = k$. and each vertex in this graph corresponds to a set $L_i$ of the graph $G$, ie, there is a bijective function $f:L_i rightarrow v_i$, $forall i, 1leq i leq k $. The edge set $E'$ of this graph is defined as $(v_i, v_i+1, forall i, 1 leq i leq k-1$. Thus, this new graph is a path graph. Similar to the original graph, each vertex in this graph is labeled with two real numbers defined by the functions $a' : v' rightarrow mathbbR$ and $b' : v' rightarrow mathbbR$ where $a'(v_i') = maxa(v), forall v in L_i$ and $b'(v_i') = minb(v), forall v in L_i$, $forall 1 leq i leq k$.
Is this formalism correct? Now we need to show that if there is a particular vertex in the new graph such that its first label value is $ge x$ then there is a path in the original graph also where there is a vertex whose first label is $ge x$. Like for instance in the example above, if $x$ is say $50$, then the third vertex in the new graph has the first label as $60 ge 50$. There is a path is the original graph where the first label is also $60 ge 50$. If this is not true provide a counterexample. I have again written this formally below.
Prove that if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') geq x$ then there is a path $v in G$ from source to sink such there is a vertex $v$ where $a(v) geq x$ and if in the path graph $G'$ there is a vertex $v'$ such that $b'(v') leq x$ then there is a path $v in G$ from source to sink such there is a vertex $v$ where $b(v) leq x$ or provide a counterexample. Is this formal definition correct?
Attempt : I tried to find a counterexample but could not find any. So for the proof attempt I tried arguing on the basis of the paths. For the first case, if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') geq x$, then let us label this path as $v_0, v_1, v_2...v_k$ and the first vertex where the label $a'$ of the vertex $ge x$ be $v_n$. Assume for the purpose of contradiction that such a path does not exist in the original graph $G$. This means that the first label of all paths in the original graph $G lt x$. When building the new graph $G'$ we assigned the label of the vertex as the maximum value of all the labels in $L_i$. As a result of this construction, we have built the new graph $G'$ and obtained a vertex where its first label is $geq$x. For this vertex to be present in the new graph $G'$ it would have to be present in the original graph $G$ as well otherwise it could not be present in the new graph $G'$. This contradicts our claim that that such a path does not exist in the original graph $G$.
Is this proof correct or am I missing something or am I on the wrong track here?
graph-theory directed-graphs
graph-theory directed-graphs
asked Mar 15 at 17:14
kauraykauray
19010
asked Mar 15 at 17:14
kauraykauray
19010
asked Mar 15 at 17:14
kauraykauray
19010
asked Mar 15 at 17:14
kauraykauray
19010
asked Mar 15 at 17:14
kauraykauray
19010
19010
add a comment |
add a comment |
0
active
oldest
votes
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%2f3149561%2fpath-property-of-directed-acyclic-graphs%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3149561%2fpath-property-of-directed-acyclic-graphs%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
