All Questions
25
questions
2
votes
4
answers
72
views
Prove $ \lg (n + 1) - 1\le h \le \lg n\implies h=\lfloor\lg n\rfloor$
For integer $n>0$ and integer $h$ prove ($lg$ means $log_2$)
$$
\lg (n + 1) - 1\le h \le \lg n\implies h=\lfloor\lg n\rfloor
$$
I'm thinking I may use $x-1<\lfloor x \rfloor \le x \le \lceil x \...
- 910
7
votes
1
answer
822
views
diameter and radius in graph and disconnected graph
We have an undirected Graph $G$.
Def $1$: The diameter of a graph is defined as the maximum of shortest paths between two vertices of $G$.
Def $2$: we define $L(S)$ as maximum length of shortest paths ...
1
vote
1
answer
100
views
shortest path not changed if one of formula is used to update all weights
Weighted Directed Graph $G$ is given. there is no negative cycle. vertexes number is $1$ to $n$. weight of edge $a$ to $b$ is $P(a,b)$. $G'$ is graph $G$ with edges will be changed according to ...
- 324
1
vote
1
answer
62
views
relation according to height factor between two specific trees
I have $2$ trees as follows:
$First$
$Second$
I want to find a relation between these two trees, I need this relation: if we get height of the second three as $H$ what is the relation between $...
- 324
0
votes
1
answer
193
views
How to prove that height of a rooted tree is an invariant under isomorphism?
Intuitively, if we're restricted to mapping the root of $T_1$ to the root of $T_2$ that makes the structure of the two trees rigid. And since under isomorphism the number of vertices are equal, height ...
- 303
1
vote
0
answers
40
views
Determining the exact form and depth of a randomized search tree
I'm working on the following task and would like to know if I did it right:
Consider a randomized search tree with values
$x_i := \frac{i^2 - log_2(i)}{2}$ and the priorities $p_i := 256 -
>...
- 4,222
3
votes
1
answer
731
views
Maximum number of nodes that may not be full in an almost complete binary tree
Assuming the following definitions:
Full Node: A full node is the root of a tree in which every non-leaf node has two children and all the leaves are at the same level/depth.
Almost Complete Tree: A ...
1
vote
2
answers
827
views
Maximum number of strict binary trees that can be made, each having exactly n leaf nodes.
I am trying to evaluate(Mathematical expression) the number of strict binary trees that can be made with n leaf nodes.
I already know that a strict binary tree with n leaf nodes would have exactly ...
2
votes
1
answer
167
views
Constructing every spanning tree from addition and deletion of edges
Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ ...
- 21
1
vote
1
answer
897
views
Closed Form for Sum of Nodes in Binary Tree
Consider a binary tree $T$ with nodes in $\mathbb{Z}^+$, where level $k$ of $T$ contains nodes $2^k$ through $2^{k + 1} - 1$. I have some problems that involve visiting the nodes of $T$ in their ...
- 1,660
2
votes
1
answer
124
views
MST, Cut in Graph, Some Claims?
I ready for taking a P.hD Entrance Exam. one of old-solution problem of Data Structure is as follows:
Which of the following Claims is True about MST of Simple, ...
- 324
2
votes
1
answer
289
views
Shortest Path Via Dynamic Programming Formulation?
We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for ...
- 79
0
votes
1
answer
2k
views
Why is the spanning tree algorithm used for bridge-routing?
In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed ...
- 4,785
2
votes
1
answer
95
views
Different trees of weighted graph , please check whether my explanation is correct $?$
Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where
$i_d$ is the number of vertices of degree $d$ in G. If S and T are two
different trees with $\xi(S) = \xi(T)$, then
...
user278174
0
votes
2
answers
692
views
How many Hamiltonian cycles are there in $K_{10,10}$? [duplicate]
I want to calculate the number of Hamiltonian cycles in $K_{10,10}.$
Could anyone help me? I think in $K_{10}$ we have $9!$ Hamiltonian
cycles.
