StŠr­frŠ­imynstur Ý t÷lvunarfrŠ­i

Weekly note 11

This week we will continue with graphs by looking at various types of graphs (8.2), graph representations and isomorphism (8.3), and finally Euler and Hamilton paths (8.5).

Next week we will start on trees from Chapter 9.

Below are 5 excercises that you are to solve and turn in to your section teacher before noon monday november 14th. Remember to mark your solutions with the number of your section and the name of the section teacher. Also below are few extra excercises that you can use to practice on and make sure that you have understood the material. Some of them will be solved in the sections if there is time.

Homework 10

  1. Exercise 6 in section 7.6 on page 528 in the textbook.

  2. Exercise 20 in section 8.1 on page 545 in the textbook. You can put values on the edges instead of drawing many edges between the same nodes.

  3. Exercise 28 a), c), e), h) in section 8.2 on page 555 in the textbook.

  4. [Exam '04] The complementary graph C(G) has the same vertices as the graph G, but an edge (u, v) is in C(G) if and only if it is not in G. Show that if G is bipartite with more than 4 vertices, then C(G) is not bipartite.

  5. Exercise 46 in section 8.2 on page 556 in the textbook.

Hand these exercices in before noon monday november 14th.

Also take a look at the following excercices:
From section 7.6:
7, 17, 27.
From section 8.1:
11, 15, 27.
From section 8.2:
5, 13, 21, 23, 35, 37.
From section 8.3:
13, 19, 35, 37, 41, 45, 55.

Remember that the above exercises are for you to practice on, and that you get the most out of them by trying to solve them yourselves (not by looking at someone else solving them!). The exercises in bold are more "interesting" than the others and it is more likely that they will be covered in the sections.

hh (hja), November 7th, 2005.