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:

$\displaystyle $0\leq w_{ij} \leq 1$$ (where w_ij is the weight of the (i,j) edge) and for each vertex i,

$\displaystyle $\sum_j{w_{ij}}\leq 1$$ (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:

$\displaystyle $0\leq w_{ij} \leq 1$$ (where w_ij is the weight of the (i,j) edge) and for each vertex i,

$\displaystyle $\sum_j{w_{ij}}\leq 1$$ (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 $\displaystyle $C_1$ $and $\displaystyle $C_2$$ consisting respectively of $\displaystyle $\nu$$ and

$\displaystyle $\rho$$ edges whose weights are

$\displaystyle $ w\left(C_1\right)= \hat{x}_{1,2} \hat{x}_{2,2} \cdots \hat{x}_{{\mu-1,}{\mu}} \cdots \hat{x}_{{\nu-1,}{1}} $ $and $\displaystyle $w\left(C_2\right) = \hat{y}_{1,2} \hat{y}_{2,3} \cdots \hat{y}_{{\pi-1,}{\pi}} \cdots \hat{y}_{{\rho-1,}{1}} $ $ where$\displaystyle $0 \leq \hat{x}_{{\mu-1,}{\mu}} \leq 1$$ is the weight of an edge in the first cycle going from vertex$\displaystyle ${\mu-1}$$ to vertex $\displaystyle ${\mu}$$ and $\displaystyle $0 \leq \hat{y}_{{\pi-1,}{\pi}} \leq 1 $$ is the weight of an edge in the second cycle going from vertex$\displaystyle ${\pi-1}$$ to vertex $\displaystyle ${\pi}$$.

In order for the two cycles to be joint we must have for some$\displaystyle $\mu$$ (in the

first cycle) and $\displaystyle $\pi$$ (in the second cycle) that $\displaystyle ${\mu-1}={\pi-1}}$$ and

$\displaystyle \hat{x}_{{\mu-1},{\mu}}+\hat{y}_{{\pi-1,}{\pi}} \leq 1 $ .................................................. ..... (1)

where$\displaystyle \hat{x}_{{\mu-1,}{\mu}$ and $\displaystyle \hat{y}_{{\pi-1,}{\pi} $are the weights

of two edges, respectively in $\displaystyle $C_1$$ and and in $\displaystyle $C_2$$, stemming from the

vertex which the two cycles share. Given $\displaystyle \hat{x}_{{\mu-1,}{\mu}}$, the

least upper bound to $\displaystyle \hat{y}_{{\pi-1}{\pi}}$ is

$\displaystyle $\left(1-\hat{x}_{{\mu-1,}{\mu}}\right)$$.

In order to calculate the least upper bound ($\displaystyle $\alpha$$) of the sum of the

weights of the cycles we build the underlying graph by adding one cycle at a

time:

$\displaystyle \alpha_1= 1$, if there is just one cycle

$\displaystyle \alpha_2=\hat{x}_{{\mu-1,}{\mu}} +\left(1-\hat{x}_{{\mu-1,}{\mu}}\right)$, if we add a second cycle

If we add a third cycle, *i)* it must have $\displaystyle 0<w\left(C_3\right)<1 $

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$\displaystyle $ \left(1-w\left(C_3\right)\right)$$. So we have:

$\displaystyle $ \alpha_3=&\hat{x}_{{\mu-1,}{\mu}}\left[1-w\left(C_3\right)\right]+\left(1-\hat{x}_{{\mu-1,}{\mu}}\right)\left[1-w\left(C_3\right)\right]+w\left(C_3\righ) $$.

The same reasoning applies if we go on adding other cycles which are pairwise joint to cycles 1, 2 and 3.