Thread: 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.

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).

Originally Posted by HappyJoe

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) }

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)}.

u are a star - thanx