Results 1 to 4 of 4

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

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    Rome - Italy
    Posts
    5

    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:
    $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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,802
    Thanks
    657

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    Rome - Italy
    Posts
    5

    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)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2012
    From
    Rome - Italy
    Posts
    5

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

    Quote Originally Posted by Maurodilettante View Post
    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.
    Last edited by Maurodilettante; November 22nd 2012 at 12:51 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 4th 2012, 04:30 PM
  2. Replies: 0
    Last Post: February 19th 2010, 01:06 AM
  3. Upper bound/Lower bound?
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: September 13th 2009, 10:48 AM
  4. Replies: 1
    Last Post: April 2nd 2008, 10:54 PM
  5. least upper bound and greatest lower bound
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 22nd 2007, 09:59 AM

Search Tags


/mathhelpforum @mathhelpforum