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

Quote:

---

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