Hey Maurodilettante.
Consider squaring the summation term where (Sigma w_ij)^2 <= 1^2 = 1 and using that kind of idea you can show that any kind of multiplication of the weights will always be less than or equal to 1.
I have n pairwise joint cycles in a weighted directed graph. For each edge, we have that:
(where w_ij is the weight of the (i,j) edge) and for each vertex i,
(i.e. the sum of the weights of the outgoing edges is less/equal 1).
If we define the weight of each cycle as the product of the weights of its edges, how can I prove that the sum of the weights of the n cycles is less/equal 1 ?
thanks a lot
Hey Maurodilettante.
Consider squaring the summation term where (Sigma w_ij)^2 <= 1^2 = 1 and using that kind of idea you can show that any kind of multiplication of the weights will always be less than or equal to 1.
Wolud the following be sufficient (and/or correct) in order to prove that the sum of the weights of the n non-disjoint cycles is less than 1?
thank you very much:
If we have two cycles and consisting respectively of and
edges whose weights are
and where is the weight of an edge in the first cycle going from vertex to vertex and is the weight of an edge in the second cycle going from vertex to vertex .
In order for the two cycles to be joint we must have for some (in the
first cycle) and (in the second cycle) that and
.................................................. ..... (1)
where and are the weights
of two edges, respectively in and and in , stemming from the
vertex which the two cycles share. Given , the
least upper bound to is
.
In order to calculate the least upper bound ( ) of the sum of the
weights of the cycles we build the underlying graph by adding one cycle at a
time:
, if there is just one cycle
, if we add a second cycle
If we add a third cycle, i) it must have
as, due to (1), the weight(s) of edge(s) stemming from the vertex(es) shared
with the first two cycles must be less than one and ii) for the
same reason, the (least upper bounds of the) weights of the other two cycles must be reduced by a factor
equal to . So we have:
.
The same reasoning applies if we go on adding other cycles which are pairwise joint to cycles 1, 2 and 3.