Maths Help

karkar athlete

Hi everyone,

I am trying to do a problem sheet for college for Finite Maths and Linear Algebra, and I am a bit stuck. I am not looking for someone to "do" the question for me, just looking for a bit of direction.....

so here the question

The intersection graph of a collection of sets A1, A2, ..,An is a graph that has a vertex for each of these sets and has an edge connecting a pair of vertices if and only if the sets repsresented by these vertices have non empty intersection.
(a) Construct the intersection graph of the following collection of sets:
A1 = {−4,−2, 0, 3, 5, 7}, A2 = {1, 3, 5, 7, 9, 11}, A3 = {−5,−3,−1, 3, 5, 7},
A4 = {0, 5, 25, 125}, A5 = {2, 4, 6, 8}, A6 = {1, 1, 3, 6, 10}
(b) Write down the number of edges in the graph constructed in (a).
(c) Write down the degree of each vertex and the sum of the degrees
of the vertices in the graph constructed in (a).


I am stuck on the A part, I am not sure how to construct the graph??? Do I plot all the points and connect them somehow or do I just place the set as a point on its own???

Thanks a million for any help

MathsManiac

You need a node called "A1", a node called "A2", etc.

If the intersection of A1 and A2 is non-empty (which it is, because 3,5, and 7 are in it), then there is an edge between A1 and A2. And so on.

Geddit?

karkar athlete

Ok so non-empty means there are elements which are in common??

So A1 is connected to A2 because it is non-empty or because because there are elements which are in common???

Anyway {3, 5, 7} are the common elements, but is it the same for A4 and A6 which have just one element in common, or are they not non-empty vertices???

And then for A5 is that an isolated vertex??

Thanks a million you are a great help

Sorry I can be a bit confusing but see I am confused myself . We had'nt come across non-empty intersection before..... :mad:

MathsManiac

I think your confusion may be caused by not understanding the set terminology. The "intersection" of two sets is the set of elements that they have in common. So, the intersection of A1 and A2 is {3, 5, 7}. This set (the intersection) is non-empty, because it has things in it.

If two sets don't have any elements in common, then their intersection is the empty set: {}.

In this question, you're told that there is an edge between two sets if their intersection is non-empty, and there is no edge if their intersection is empty.

To have an edge between two nodes (sets), it doesn't matter how many elements are in the intersection, as long as there is at least one.

A5, as you have observed, does not share any elements with any of the others, so its intersection with any of the others is always empty. So you are correct: it will not have any edges incident to it, and it is an isolated node.

hivizman

MathsManiac wrote: »

A5, as you have observed, does not share any elements with any of the others, so its intersection with any of the others is always empty. So you are correct: it will not have any edges incident to it, and it is an isolated node.

The intersection of A5 and A6 is not empty - both sets contain 6.

Just as a point of detail, should A6 be {-1, 1, 3, 6, 10} rather than {1, 1, 3, 6, 10}? It doesn't make any difference to the answer, but it looks odd that an element is repeated.

karkar athlete

Thanks a million MathsManic, that cleared it upagreat deal, :P after you said there was a non-empty intersection between A1, A2 and A3 I thought the three elements {3, 5, 7} had to be in the othersets in order for them to be connected. Thanks. So just making sure there is a connection between two vertices once they have an element in common??

hivizman wrote: »

The intersection of A5 and A6 is not empty - both sets contain 6.

Just as a point of detail, should A6 be {-1, 1, 3, 6, 10} rather than {1, 1, 3, 6, 10}? It doesn't make any difference to the answer, but it looks odd that an element is repeated.

And Hivizman thanks I didn't see that. :rolleyes: And your point about A6 is questioning, but i copied the question straight from the problem sheet, but it could be a mistake because there are a couple of spelling errors on it. :eek: And it does in fact change the graph contructed, if A6 was {-1, 1, 3, 6, 10} it would be connected to A3.

Thanks a million both of you for you help

MathsManiac

hivizman wrote: »

The intersection of A5 and A6 is not empty - both sets contain 6.

Just as a point of detail, should A6 be {-1, 1, 3, 6, 10} rather than {1, 1, 3, 6, 10}? It doesn't make any difference to the answer, but it looks odd that an element is repeated.

Thanks! Hadn't spotted that (obviously!)

hivizman

karkar athlete wrote: »

And Hivizman thanks I didn't see that. :rolleyes: And your point about A6 is questioning, but i copied the question straight from the problem sheet, but it could be a mistake because there are a couple of spelling errors on it. :eek: And it does in fact change the graph contructed, if A6 was {-1, 1, 3, 6, 10} it would be connected to A3.

A3 and A6 both contain 3, so they are connected anyway.