Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [trees]

For questions about trees in graph theory, which are connected graphs with no cycles. Also can be used for questions about forests, which are graphs that are disjoint unions of trees.

Trees are an important topic in graph theory. A tree is a connected graph with no cycles. They are of enormous practical importance in applied mathematics.

For example, in a connected weighted graph, it is interesting to know how to find a subgraph which is a tree and which maximizes or minimizes the total weight of the subgraph. A subgraph of a graph $G$ which is a tree that touches all nodes of $G$ is called a spanning tree for $G$.

For instance, imagine a network of electrical systems, such as a telephone system, between nodes. Suppose that signals can travel through any path in the network, passing through intervening nodes to get to the final destination. The amount of wiring can be reduced by deleting portions of cycles in the graph of the network. The graph can eventually be reduced to a tree, and all nodes remain connected and accessible through the network.

Dijkstra's algorithm is an effective way to determine the lowest-weight spanning tree for a given connected graph.

2015 questions
2
votes
1 answer

questions about binary search tree

Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees. How is it prove mathematical? Please, help
alex
  • 21
2
votes
1 answer

Adding one edge to a tree creates exactly one cycle

I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle supposedly a closed chain path ?
greatShark
  • 21
2
votes
1 answer

Oriented trees and ordered trees

I have this confusion regarding ordered and oriented trees. I know they are both rooted and in ordered trees, the order is important. So lets say I have four nodes 1,2,3,4 then it is given that the number of ordered trees is 5. How come this is…
rajan sthapit
  • 449
  • 1
  • 5
  • 13
2
votes
1 answer

A tree has a root, leaves, and what?

The root of a tree is special, in that it has no parents. The leaves are special in that they have no children. The other nodes each have exactly one parent and more than zero children. Is there a word for that third kind? (Myself, I have been…
Jeffrey Benjamin Brown
  • 21
2
votes
1 answer

Prove in any tree with n vertices, the number of nodes with 3 or more neighbors is at most 2(n-1)/3

I know that the number of edges in the tree is n-1, and by the sum identity, the degree is 2(n-1)... I'm not sure how to go about completing the proof, or even starting it for that matter.
user1822739
  • 23
1
vote
0 answers

Multiway tree to Binary Tree

A multiway tree T can be represented as a binary tree T~ by using the firstChild and nextSibling pointers. If we think of the firstChild link as being the left link and the nextSibling link as being the right link, then we can traverse this binary…
girl101
  • 333
1
vote
1 answer

Postorder and Preorder traversal on a Binary tree

For the tree below, list the labels of the nodes of the tree according to the pre-ordering algorithm, and then re-list them according to the post-ordering algorithm. 1 / \ …
Mark Spencer
  • 13
1
vote
1 answer

Number of distinct Binary tree formed with respect to height h

How many types of distinct Binary Tree can be formed with a height of h? assuming height starts from 0 when the tree has only the root. example: if the height of tree is 1 then root-leftchild root-rightchild root-leftchild-rightchild are the…
girl101
  • 333
1
vote
2 answers

syntax tree for the word (())()()

I have to create the syntax tree for the word (())()() . That's what I have tried: Could you tell me if it is right?
evinda
  • 7,823
1
vote
0 answers

For which graphs do depth first and breadth first produce identical spanning trees?

Is this possible?If yes, what are the conditions it should meet?
kanv
  • 31
1
vote
1 answer

Shortest path joining two paths on tree

Let $[a, b]$ and $[c, d]$ be two paths on a tree network with empty intersection. It is easy to observe that: The intersection of paths [x, y], where $x\in [a, b]$ and $y\in [c, d]$, is again a non-empty path, say $[r, s]$ here $r\in [a, b]$ and…
Leonard Neon
  • 1,354
1
vote
0 answers

AVL Binary Tree: Loneliness Rate

A node in a binary tree is an only child if it has a parent node, but has no sibling (note that the root is not qualified as an only child). The “loneliness rate” (LR) of a binary tree T is defined as follows: $$ LR = \frac{\text{number of $T$ nodes…
L. WD
  • 11
1
vote
0 answers

Red Black Binary Search Trees

Give an example of a Red-Black tree and a value, for which inserting the value, and then immediately deleting it yields a tree that is different from the tree before the insertion.
Davian Kal'El Litchmore
  • 11
  • 2
1
vote
1 answer

Questions on DFS

Question: if I assume that I ran Depth First Search on a digraph $G,$ and obtained a directed spanning forest $F.$ I am interested in the set $R$ of vertices reachable from a given fixed vertex $a \in V (G).$ How do I Show in general set $R$ of…
TheCodeLearner
  • 35
  • 4
1
vote
0 answers

Determine the treewidth of the graph by proving matching upper and lower bounds

I have determined the lower bound to be 3, but have failed to find any theory or lemmas on how to find the upper bound. Any advice is helpful.
rumetalmI
  • 97
1
2
3 4 5 6