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

**Maurodilettante** · November 1st 2012, 11:47 AM

I have n pairwise joint cycles in a weighted directed graph. For each edge, we have that:
$0\leq w_{ij} \leq 1$ (where w_ij is the weight of the (i,j) edge) and for each vertex i,
$\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

**chiro** · November 1st 2012, 07:02 PM

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.

**Maurodilettante** · November 3rd 2012, 10:04 AM

Thank you very much Chiro,
I will follow your suggestion (although I fear that my problem is also with the sum of the products)

**Maurodilettante** · November 22nd 2012, 04:36 AM

Originally Posted by Maurodilettante

I have n pairwise joint cycles in a weighted directed graph. For each edge, we have that:
$0\leq w_{ij} \leq 1$ (where w_ij is the weight of the (i,j) edge) and for each vertex i,
$\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 $C_1$ and $C_2$ consisting respectively of $\nu$ and
$\rho$ edges whose weights are
$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 $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 $0 \leq \hat{x}_{{\mu-1,}{\mu}} \leq 1$ is the weight of an edge in the first cycle going from vertex ${\mu-1}$ to vertex ${\mu}$ and $0 \leq \hat{y}_{{\pi-1,}{\pi}} \leq 1$ is the weight of an edge in the second cycle going from vertex ${\pi-1}$ to vertex ${\pi}$ .
In order for the two cycles to be joint we must have for some $\mu$ (in the

first cycle) and $\pi$ (in the second cycle) that ${\mu-1}={\pi-1}}$ and
$\hat{x}_{{\mu-1},{\mu}}+\hat{y}_{{\pi-1,}{\pi}} \leq 1$ .................................................. ..... (1)
where $\hat{x}_{{\mu-1,}{\mu}$ and $\hat{y}_{{\pi-1,}{\pi}$ are the weights
of two edges, respectively in $C_1$ and and in $C_2$ , stemming from the
vertex which the two cycles share. Given $\hat{x}_{{\mu-1,}{\mu}}$ , the
least upper bound to $\hat{y}_{{\pi-1}{\pi}}$ is

$\left(1-\hat{x}_{{\mu-1,}{\mu}}\right)$ .
In order to calculate the least upper bound ( $\alpha$ ) of the sum of the

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

time:
$\alpha_1= 1$ , if there is just one cycle
$\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 $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 $\left(1-w\left(C_3\right)\right)$ . So we have:
$\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.

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

LinkBack

Thread Tools

Display

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

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

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

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

Similar Math Help Forum Discussions

glb and lub (greatest lower bound and least upper bound)

Partial sets/ Least upper bound/Greastest lower bound/Lattices

Upper bound/Lower bound?

What is the upper & lower bound of 1.0 to one dec. place?

least upper bound and greatest lower bound

Search Tags