Mixing
If an orientation of a tree graph has no source vertices, must the in-degree of each vertex in said orientation be equal to one?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Given any polytree $T$ (any orientation of a tree graph) such that $forall vin V(T)(textindeg(v)neq 0)$ does this imply that $forall vin V(T)(textindeg(v)=1)$? I'm pretty sure its true, but I'm having a rather hard time constructing a proof. Also it's clear that any such digraph $T$ is non-finite, since any directed acyclic graph with no source vertices must necessarily contain an in-ray and thus can't be finite.
graph-theory trees orientation directed-graphs
asked yesterday
Ethan
6,70811863
add a comment |Â
up vote
1
down vote
favorite
Given any polytree $T$ (any orientation of a tree graph) such that $forall vin V(T)(textindeg(v)neq 0)$ does this imply that $forall vin V(T)(textindeg(v)=1)$? I'm pretty sure its true, but I'm having a rather hard time constructing a proof. Also it's clear that any such digraph $T$ is non-finite, since any directed acyclic graph with no source vertices must necessarily contain an in-ray and thus can't be finite.
graph-theory trees orientation directed-graphs
asked yesterday
Ethan
6,70811863
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Given any polytree $T$ (any orientation of a tree graph) such that $forall vin V(T)(textindeg(v)neq 0)$ does this imply that $forall vin V(T)(textindeg(v)=1)$? I'm pretty sure its true, but I'm having a rather hard time constructing a proof. Also it's clear that any such digraph $T$ is non-finite, since any directed acyclic graph with no source vertices must necessarily contain an in-ray and thus can't be finite.
graph-theory trees orientation directed-graphs
asked yesterday
Ethan
6,70811863
Given any polytree $T$ (any orientation of a tree graph) such that $forall vin V(T)(textindeg(v)neq 0)$ does this imply that $forall vin V(T)(textindeg(v)=1)$? I'm pretty sure its true, but I'm having a rather hard time constructing a proof. Also it's clear that any such digraph $T$ is non-finite, since any directed acyclic graph with no source vertices must necessarily contain an in-ray and thus can't be finite.
graph-theory trees orientation directed-graphs
asked yesterday
Ethan
6,70811863
edited yesterday
asked yesterday
Ethan
6,70811863
asked yesterday
Ethan
6,70811863
asked yesterday
Ethan
6,70811863
6,70811863
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Counterexample:
$$ cdots to bullet to bullet to bullet leftarrow bullet leftarrow bullet leftarrow cdots $$
(A doubly-infinite path with all edges pointing towards a designated center).
answered yesterday
Henning Makholm
225k16289516
One can prove that a finite digraph is an arborescence if and only if its a polytree with one source vertex. Where an abhorrence is a connected acyclic digraph all of whose vertices (other then possibly a source vertex) have an in-degree of one. With that said I was hoping to try and fiind some criteria for abhorrences with no source vertex involving polytrees. Do you think its possible to add more preliminary restrictions to my polytree to ensure that every vertex has in-deree of one? Where again its clear none of these polytrees are going to be finite.
– Ethan
yesterday
@Ethan: You can take an arbitrary infinite rooted tree without leaves and point all edges towards the root. Then you can have as large indegrees as you want to.
– Henning Makholm
yesterday
Ahh damnet. I think the finite result hinges on the fact that a directed acyclic graph is rooted iff it has one source vertex. Thanks anyway though.
– Ethan
yesterday
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Counterexample:
$$ cdots to bullet to bullet to bullet leftarrow bullet leftarrow bullet leftarrow cdots $$
(A doubly-infinite path with all edges pointing towards a designated center).
answered yesterday
Henning Makholm
225k16289516
One can prove that a finite digraph is an arborescence if and only if its a polytree with one source vertex. Where an abhorrence is a connected acyclic digraph all of whose vertices (other then possibly a source vertex) have an in-degree of one. With that said I was hoping to try and fiind some criteria for abhorrences with no source vertex involving polytrees. Do you think its possible to add more preliminary restrictions to my polytree to ensure that every vertex has in-deree of one? Where again its clear none of these polytrees are going to be finite.
– Ethan
yesterday
@Ethan: You can take an arbitrary infinite rooted tree without leaves and point all edges towards the root. Then you can have as large indegrees as you want to.
– Henning Makholm
yesterday
Ahh damnet. I think the finite result hinges on the fact that a directed acyclic graph is rooted iff it has one source vertex. Thanks anyway though.
– Ethan
yesterday
add a comment |Â
up vote
1
down vote
accepted
Counterexample:
$$ cdots to bullet to bullet to bullet leftarrow bullet leftarrow bullet leftarrow cdots $$
(A doubly-infinite path with all edges pointing towards a designated center).
answered yesterday
Henning Makholm
225k16289516
One can prove that a finite digraph is an arborescence if and only if its a polytree with one source vertex. Where an abhorrence is a connected acyclic digraph all of whose vertices (other then possibly a source vertex) have an in-degree of one. With that said I was hoping to try and fiind some criteria for abhorrences with no source vertex involving polytrees. Do you think its possible to add more preliminary restrictions to my polytree to ensure that every vertex has in-deree of one? Where again its clear none of these polytrees are going to be finite.
– Ethan
yesterday
@Ethan: You can take an arbitrary infinite rooted tree without leaves and point all edges towards the root. Then you can have as large indegrees as you want to.
– Henning Makholm
yesterday
Ahh damnet. I think the finite result hinges on the fact that a directed acyclic graph is rooted iff it has one source vertex. Thanks anyway though.
– Ethan
yesterday
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Counterexample:
$$ cdots to bullet to bullet to bullet leftarrow bullet leftarrow bullet leftarrow cdots $$
(A doubly-infinite path with all edges pointing towards a designated center).
answered yesterday
Henning Makholm
225k16289516
Counterexample:
$$ cdots to bullet to bullet to bullet leftarrow bullet leftarrow bullet leftarrow cdots $$
(A doubly-infinite path with all edges pointing towards a designated center).
answered yesterday
Henning Makholm
225k16289516
answered yesterday
Henning Makholm
225k16289516
answered yesterday
Henning Makholm
225k16289516
answered yesterday
Henning Makholm
225k16289516
225k16289516
One can prove that a finite digraph is an arborescence if and only if its a polytree with one source vertex. Where an abhorrence is a connected acyclic digraph all of whose vertices (other then possibly a source vertex) have an in-degree of one. With that said I was hoping to try and fiind some criteria for abhorrences with no source vertex involving polytrees. Do you think its possible to add more preliminary restrictions to my polytree to ensure that every vertex has in-deree of one? Where again its clear none of these polytrees are going to be finite.
– Ethan
yesterday
@Ethan: You can take an arbitrary infinite rooted tree without leaves and point all edges towards the root. Then you can have as large indegrees as you want to.
– Henning Makholm
yesterday
Ahh damnet. I think the finite result hinges on the fact that a directed acyclic graph is rooted iff it has one source vertex. Thanks anyway though.
– Ethan
yesterday
add a comment |Â
One can prove that a finite digraph is an arborescence if and only if its a polytree with one source vertex. Where an abhorrence is a connected acyclic digraph all of whose vertices (other then possibly a source vertex) have an in-degree of one. With that said I was hoping to try and fiind some criteria for abhorrences with no source vertex involving polytrees. Do you think its possible to add more preliminary restrictions to my polytree to ensure that every vertex has in-deree of one? Where again its clear none of these polytrees are going to be finite.
– Ethan
yesterday
@Ethan: You can take an arbitrary infinite rooted tree without leaves and point all edges towards the root. Then you can have as large indegrees as you want to.
– Henning Makholm
yesterday
Ahh damnet. I think the finite result hinges on the fact that a directed acyclic graph is rooted iff it has one source vertex. Thanks anyway though.
– Ethan
yesterday
One can prove that a finite digraph is an arborescence if and only if its a polytree with one source vertex. Where an abhorrence is a connected acyclic digraph all of whose vertices (other then possibly a source vertex) have an in-degree of one. With that said I was hoping to try and fiind some criteria for abhorrences with no source vertex involving polytrees. Do you think its possible to add more preliminary restrictions to my polytree to ensure that every vertex has in-deree of one? Where again its clear none of these polytrees are going to be finite.
– Ethan
yesterday
One can prove that a finite digraph is an arborescence if and only if its a polytree with one source vertex. Where an abhorrence is a connected acyclic digraph all of whose vertices (other then possibly a source vertex) have an in-degree of one. With that said I was hoping to try and fiind some criteria for abhorrences with no source vertex involving polytrees. Do you think its possible to add more preliminary restrictions to my polytree to ensure that every vertex has in-deree of one? Where again its clear none of these polytrees are going to be finite.
– Ethan
yesterday
@Ethan: You can take an arbitrary infinite rooted tree without leaves and point all edges towards the root. Then you can have as large indegrees as you want to.
– Henning Makholm
yesterday
@Ethan: You can take an arbitrary infinite rooted tree without leaves and point all edges towards the root. Then you can have as large indegrees as you want to.
– Henning Makholm
yesterday
Ahh damnet. I think the finite result hinges on the fact that a directed acyclic graph is rooted iff it has one source vertex. Thanks anyway though.
– Ethan
yesterday
Ahh damnet. I think the finite result hinges on the fact that a directed acyclic graph is rooted iff it has one source vertex. Thanks anyway though.
– Ethan
yesterday
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2872401%2fif-an-orientation-of-a-tree-graph-has-no-source-vertices-must-the-in-degree-of%23new-answer', 'question_page');
);
Post as a guest
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
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
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