Quick homework question

[GodlessAstronomer]

The problem is a list of university math courses that are restricted against one another, for example

Course: restrictions
102: 110,112
103: 110,111

etc.

Construct a graph showing the pairs of courses which may not be credited together.

Am I correct that this is a simple graph coloring problem? Courses of different colors can not be credited together? Or is there something more complex involved?

Thanks.

 

[TuxDave]

It looks like just a simple connected graph where neighboring nodes cannot be credited together. If you start applying color and have 102 red, 110 blue and 112 yellow. It satisfies the condition that neighboring nodes have different colors but doesn't address the actual restriction. You're ok to get 110 and 112 even though they're different colors.

<-- haven't taken graph theory forever so maybe I'm off base.

Even for just the example you gave" I guess it would be a straight line of:

112 -- 102 -- 110 -- 103 -- 111

If you did a colored graph it would be
R-B-R-B-R

But you can take 103 and 112 and get credit even if it's different colors.

 

[GodlessAstronomer]

Originally posted by: TuxDave
It looks like just a simple connected graph where neighboring nodes cannot be credited together. If you start applying color and have 102 red, 110 blue and 112 yellow. It satisfies the condition that neighboring nodes have different colors but doesn't address the actual restriction. You're ok to get 110 and 112 even though they're different colors.

<-- haven't taken graph theory forever so maybe I'm off base.

Yep, you're right, after drawing the graph it became obvious that this wasn't the correct solution. Looks like an independent sets problem. I missed that lecture Better start reading the text book.