0
Prove that if a DFS and BFS trees in graph G are the same than?
Wiki User
∙ 16y ago
ok here we go...
Proof:
If the some graph G has the same DFS and BFS then that means that G should not have any cycle(work out for any G with a cycle u will never get the same BFS and DFS .... and for a graph without any cycle u will get the same BFS/DFS).
We will prove it by contradiction:
So say if T is the tree obtained by BFS/DFS, and let us assume that G has atleast one edge more than T. So one more edge to T(T is a tree) would result in a cycle in G, but according to the above established principle no graph which has a cycle would result the same DFS and BFS, so out assumption is a contradiction.
Hence G should have more edges than T, which implies that if the BFS and DFS for a graph G are the same then the G = T.
Hope this helps u......................
Wiki User
∙ 16y ago
Add your answer:
Earn +20 pts
What is Difference between tree and spanning tree?
A tree is a connected graph in which only 1 path exist between any two vertices of the graph i.e. if the graph has no cycles. A spanning tree of a connected graph G is a tree which includes all the vertices of the graph G.There can be more than one spanning tree for a connected graph G.
Is it true that parallel circuits and series circuits have no similarity?
No. It is true they are not the same, which is completely different than saying they share nothing in common. An apple and an orange are not the same, but they are similar in that they are both fruit, grow on trees, need sunlight to grow, are generally considered good breakfast juices, etc.
What is the practical application for a binary converter?
The reason that binary trees are used more often than n-ary trees for searching is that with every contract with an n-ary tree you can eliminate most of it.
Which is better - AVL or Red Black Trees?
It depends on what the tree is being used for. If the tree is being used to store data that is not going to be modified very much, than AVL trees are probably better. In most other cases, I'd say Red-Black trees are better.
What is made of softwood?
Softwood is just normal wood from a tree, but it's only wood from certain types of trees. All the pine and fir trees are softwood trees (conifers) and the leafy trees like oaks and maples (deciduous) are hardwood trees. The difference is literally that conifers produce a softer, more easily dented wood than deciduous.
What is a frequency graph?
A graph that used the same one of the numbers more than once.
How can a table be more informative than the graph with the same data?
A graph can be more useful for making presentations because it is more visual, and it can be easier to recognize a pattern in a graph for the same reason. However, a graph doesn't have any more data than a table with the same data.
How can you tell whether a graph is a function or not?
A vertical line test can be used to determine whether a graph is a function or not. If a vertical line intersects the graph more than once, then the graph is not a function.
How can a graph of data be more informative than a table of the same data?
A graph will show a visual pattern of date, which makes it much easier to recognize and understand.
Would our lives be the same if all trees lived for less than a hundred year?
yes it will be the same.
How can a graph of data be more information than a table of the same data?
It does not. In fact, it usually contains less information because some of the precision of the data in the table may not be easy to retrieve from the graph. However, many people (but not all) find it easier to get a summarised version of the information from a graph than from a table.
Is a column graph easier to understand than a picture graph?
no
How do you graph inequalities in two variables?
to graph in equaltities in two variables, you graph the two numbers and/or variables. then you look at the sign to see if its greater than, less than, greater than or equal to, or less than or equal to and you graph the line as dashed or a solid
Why do trees look different than others?
Well there are many different types of trees, so each type of tree doesn't look the same. As for trees of the same type of tree, they may be different sizes because of the age differences.
Why is a bar graph or pictograph is more suitable to use than another type of graph?
Because a bar graph and pictographs are more visual and labelled than any other type of graph.
Is a stacked bar graph better than a double bar graph?
no a double bar graph is better
What is the results from 2000 to 2008 on the population of cutting down trees in a graph?
The population of tree growth would actually be higher than the amount being cut down. This is because the world has started to plant more trees as they cut down old ones.
