Let KM,N be a complete bipartite graph and A be a (M,N) positive matrix. We call one part of vertices left and the other right. Two spanning trees T1 and T2 are in the same class when they have the same right degrees. A spanning tree T of KM,N uniquely determines a vector (w, p) = (wi, pj) = v(T) up to scalar multiplication, where wi is a value of a left vertex and pj is one of right vertex. A tree T is said to be admissible with regards to A, when the T-defined value v(T) = (w, p) satisfies inequalities
wi aij ≧ pj ∀ (i,j) and wi aij = pj ∀ (i,j) ∈ T. (1)
I want to know if there is a good algorithm that computes an admissible tree (or a set of all admissible trees) for a given A.
If A is in a general position, it is known that there is only one admissible tree that is in a given class when the left degrees sums up to M+N-1.
This question is closely related to following two of my questions:
Do you know the number of all spanning trees of a given class?https://www.researchgate.net/post/Do_you_know_the_number_of_all_spanning_trees_of_a_given_class
A Conjecture on Trees in a Complete Bipartite Graph: does two trees of the same class have a cycle with opposite orientations?https://www.researchgate.net/post/A_Conjecture_on_Trees_in_a_Complete_Bipartite_Graph_does_two_trees_of_the_same_class_have_a_cycle_with_opposite_orientations/1
This question consists of my research on theory of Ricardo trade economy. See the 9th post to the above question under the title Ricardo trade economy.
I don't know of an algorithm offhand, but I wouldn't be surprised if one existed. There's a modification of the Prufer code proof of Cayley's formula which allows you to count trees with a given degree sequence in the complete graph K_n.
Is this question difficult?
If we check all spanning trees of a given class if they satisfy the inequality (1). I am asking if someone knows more rapid algorithm.
Another possible formulation of the question:
My question may be reformulated as follows:
Let KM,N be a complete bipartite graph. Each edge is labeled by a real number b(i,j). When each vertex is given a real number, the set of such numbers is called vertex labeling and we write as a couple of two vectors s = {s(i) } and t = {t(i)}.
The original problem is expressed in multiplicative way. If we put
b(i,j) = log aij,
the question of this page is transformed to the following question. This may be a well known problem in tropical oriented matroid theory.
A spanning tree T is admissible when there is a vertex labeling {s, t} such that
s(i) + b(i,j) ≧ t(j) ∀ (i,j) ∈ M×N
and
s(i) + b(i,j) = t(j) ∀ (i,j) ∈T.
A left class (or right class) is given by a set of positive integers h = {h(i)} (or h = {h(j) respectively} when
h(1)+ ... + h(M or N) = M+N-1.
It is known that there is only one admissible spanning tree in a given left (or right) class. The problem is to find a fast algorithm which gives this unique spanning tree.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Control Theory
- Control Systems