Results 1 to 5 of 5

Math Help - What is a restriction in a set?

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    23

    What is a restriction in a set?

    I am doing self study on graph theory and they use sets. I am reading a paper about how to find patterns in graphs. And they define a sub-graph using sets.

    Graph G = (V, E, L) where V, E, L are sets of verticies, edges and lables.
    G' = (V', E', L') is a sub-graph if:

    V' is a sub set of V
    E' is the set E intersect (V' x V')

    All this is fine and i get that.

    But: L' is a restriction of L on V' U E'

    2 questions:
    What is a restriction in set theory?
    How do I union V' and E' as V is a set of verticies {1, 2, 3, 4} and E' is a set of oredered pairs { (1,2), (1,3), (2,3), (2,4)}

    Kind regards

    Richard.
    Last edited by brennan; October 24th 2010 at 03:07 AM. Reason: spelling errors
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    In graph theory, labels can be assigned to either vertices or edges (or both), and I guess that your article attempts to cover both cases.

    As for the restriction question, you can consider L as a function from V U E into some set of labels, i.e. L takes either a vertex or an edge and gives it some label. The set V' U E' is just a subset of V U E, and so you define L' to be the restriction of L (as a function) to the set V' U E'. Do you know what the restriction of a function means?

    As for the union of V' and E', where V' = {1,2,3,4} and E' = {(1,2), (1,3), (2,3), (2,4) }, it is just that:

    V' U E' = {1,2,3,4, (1,2), (1,3), (2,3), (2,4)},

    so V' U E' is a set, in which elements are either vertices or edges (they have been mixed, so to speak).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    23
    Quote Originally Posted by HappyJoe View Post
    In graph theory, labels can be assigned to either vertices or edges (or both), and I guess that your article attempts to cover both cases.

    As for the restriction question, you can consider L as a function from V U E into some set of labels, i.e. L takes either a vertex or an edge and gives it some label. The set V' U E' is just a subset of V U E, and so you define L' to be the restriction of L (as a function) to the set V' U E'. Do you know what the restriction of a function means?

    As for the union of V' and E', where V' = {1,2,3,4} and E' = {(1,2), (1,3), (2,3), (2,4) }, it is just that:

    V' U E' = {1,2,3,4, (1,2), (1,3), (2,3), (2,4)},

    so V' U E' is a set, in which elements are either vertices or edges (they have been mixed, so to speak).
    Thanx for that:

    Can you clarify the L restriction thing with the following example.

    G = (V, E, L)

    V = {1, 2, 3, 4, 5};
    E = {(1,2), (1,3), (1, 4), (3, 4), (3,5), (5,4)}
    L = {a, b, c, d, e} - how do you assiciate a lable with the appropriate edge?
    (I have never seen the set L, does it need to contain oreder tripls like (1,2, a)? )

    Now lets consider sub graph

    G' = (V', E' L')

    V' = {3, 4, 5}
    E' = E intersect (V' x V')
    V' x V' = {(3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5) }
    E' = E intersect = {(3,4), (3,5), (5,4) }

    That I'm cool with - can you now explain

    L' is a restriction of L on V' U E'
    or
    L' is a restriction of L on {3, 4, 5, (3,4), (3,5), (5,4) }
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    L is just a function from the union of V and E into some set of labels, which you may denote by {a,b,c,d,e} in this case. One way of writing L is somewhat like you suggest, i.e. if L maps the object x to the label y, then (x,y) is an element of L. So for example, if the vertex 1 has label b, vertex 2 has label d, and whatnot for the other vertices, and perhaps the edge (1,2) has label a and so on with the other edges, then L as a set looks like

    L = {(1,b), (2,d), (3,a), (4,a), (5,b), ((1,2),a), ((1,3),b), ((1,4),e), ((3,4),d), ((3,5),d), ((5,4),c)}.

    This show you exactly what labels each vertex and each edge have been given.

    Now you want the restriction L' of L to V' U E', where V' U E' = {3, 4, 5, (3,4), (3,5), (5,4)}. For this purpose, you include in L' only those elements (x,y) of L for which x can be found in V' U E'. So we need the elements of L, whose first entries are 3, 4, 5, (3,4), (3,5), and (5,4), and we leave all others.

    Hence L' = {(3,a), (4,a), (5,b), ((3,4),d), ((3,5),d), ((5,4),c)}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2010
    Posts
    23
    u are a star - thanx
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Function restriction.
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: November 26th 2011, 05:37 PM
  2. restriction of sigma-algebra
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 15th 2011, 05:37 AM
  3. restriction
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 26th 2010, 03:39 PM
  4. Graph of restriction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 20th 2010, 09:11 AM
  5. Restriction of a Set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 13th 2009, 01:11 AM

Search Tags


/mathhelpforum @mathhelpforum