diigraph: lower upper bound of the sum of the weights of n pairwise joint cycles

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

Re: diigraph: lower upper bound of the sum of the weights of n pairwise joint cycles

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.

Re: diigraph: lower upper bound of the sum of the weights of n pairwise joint cycles

Thank you very much Chiro,

I will follow your suggestion (although I fear that my problem is also with the sum of the products)

[?] digraph: lower upper bound of the sum of the weights of n pairwise joint cycles

Quote:

Originally Posted by

**Maurodilettante** 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

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.