Is Diagram 2 a tree of the undirected graph in Diagram 1 ?
- Thread starter JHY
- Start date
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,617
You know how this site works, right?
Please tell us your thoughts. What definition have you been given for a tree of a graph? Does this fit that definition? What part of the problem are you unsure of?
What I know about a tree is that "A tree is a type of subgraph which :
i) is a simple graph which should not contain a loop or multi-edge
ii) every vertex is connected , no cycles exist
iii) number of edges = number of vertex - 1
What I am unsure of is that when making a tree out of a network, can a vertex be omitted, or must all the vertex be included in a tree ? In the question above, the original network in diagram 1 has 6 vertex. Then in diagram 2, a tree is formed out of the original network, but vertex U is omitted. Diagram 2 satisfied all the condition for a tree but it omitted vertex U from the original network. Is it still a tree? although it does not include all the 6 vertex ? All is it not a tree, because it does not have all the 6 vertex ?
i) is a simple graph which should not contain a loop or multi-edge
ii) every vertex is connected , no cycles exist
iii) number of edges = number of vertex - 1
What I am unsure of is that when making a tree out of a network, can a vertex be omitted, or must all the vertex be included in a tree ? In the question above, the original network in diagram 1 has 6 vertex. Then in diagram 2, a tree is formed out of the original network, but vertex U is omitted. Diagram 2 satisfied all the condition for a tree but it omitted vertex U from the original network. Is it still a tree? although it does not include all the 6 vertex ? All is it not a tree, because it does not have all the 6 vertex ?
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,617
Thanks. This helps in understanding your issue.
Now, what is the definition of a subgraph? Can it omit a vertex?
What you say about a tree is not quite a definition. The last line is a fact that can be derived from the definition; and the first two lines are not coherent, in that I would have expected, say, being connected to relate to having no cycles, from the way you combine them. Also, a tree doesn't have to be a subgraph; that's what it means to be a tree "of a graph".
Here is an example of an actual definition (though different sources often use somewhat different terminology, so this may differ from what you have been taught):
In graph theory, tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.
Here is another:
Sometimes this is stated as “a tree is an acyclic connected graph;” “acyclic” is just a fancy word for “containing no cycles.”
So there are basically two requirements: connected, and no cycles. In your question, in addition it should be a subgraph of the given graph.
If you search for "tree of a graph", you will probably find references to a "spanning tree of a graph". Can you guess what additional property is meant by "spanning"?
Does that help answer your question. (I'm trying not to directly answer it, so you can learn to use definitions to answer your own questions.)
I try to search for the meaning of "spanning tree of a graph" in the internet, and I found this definition:
" A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices."
So my diagram 1 is a disconnected graph as vertex U is unconnected. So it is impossible to get a spanning tree out of diagram 1. Therefore diagram 2 is a tree, but it is not a spanning tree of diagram 1. Am I right ?
" A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices."
So my diagram 1 is a disconnected graph as vertex U is unconnected. So it is impossible to get a spanning tree out of diagram 1. Therefore diagram 2 is a tree, but it is not a spanning tree of diagram 1. Am I right ?
