Graph Theory   page

My teaching schedule is: Tu-Th 5:00PM - 6:15PM, GC 272

My office hours are on Tuesday, 3.45 pm-4.30 pm. Thursday,1.30pm-3pm or by appointment.

Office: DM 436B.

Up-to-date information and downloads (Last update: Nov. 20)

Test 1 and Homework 1.

The brand new computer in my office has crashed a number of time and some of my files have been lost or corrupted. I may have lost the corrections that I have made on the grades of Homework 1 and Test 1, so, just to be sure, I need you to bring to class Tests 1 and Homework 1. Thank you in advance!! 

Tests

The third test is on Tuesday, Nov. 24. A review sheet for the test is below.
Here is also a list of theorems that may be in the test. 
 

1) Let v be a vertex that is incident to a bridge, then v is a cut  vertex iff deg(v)>=2

2) v is a cut vertex if and only if there exist two vertices u and w such that v  lies in every (u,w) path

3)Let G be a connected graph and u be a vertex of G, then the vertex  for which dist (u,v) is maximum is not a cut vertex

4) Every graph contains at least two vertices that are NOT cut-vertices

5) For a given tree T, all vertices that are not end vertices, are cut  vertices

6) if every two vertices of G lie on a cycle then G is separable (We have done only one part of Theorem 5.7)

7) Two blocks don't have any edge in common

8)If two blocks have a vertex in common then the vertex is a cut  vertex.

9) If a graph is Eulerian then the degree of each vertex is even (in class we have covered both implication but in the test I may ask only the easier one)

10) A graph has an Eulerian trail if and only if exactly two vertices of G have odd degree

11) If S is a set of vertices of an Hamiltonian graph G, then for the connected components of G-S are at least as many as the vertices in S.

Homework.

 
 
 
These problems are part of Homework 3. It is due on Tuesday, Nov. 17. 
 

1) Consider the graph that is now at the top of the page. Use the Dijkstra’s algorithm to find the less expensive path between the vertices a and h. Justify your steps with an appropriate matrix.
2) Find also a minimum spanning tree for this graph.
3) A company has branches in six cities. The table of the cost of the direct flight between cities is below (“infinity” means that there is no direct flight). 

The company wants to determine a table of the cheapest route between pair of cities. Determine such table.

 
Section 5.1. 5.2, 5.4, 5.6
Section 5.2. 5.9, 5.12
Section 6.1. 6.1, 6.2, 6.4, 6.6

 
 
These are extra problems that will serve as a preparation for Test 3 and the final.
I will collect these problems before the final; they will count for extra credit toward the homework.
 
Section 6.2. 6.10, 6.14, 6.16, 6.21, 6.22 
 
______________________________________________________________________________________________ 
 
These are the problems for Hw1.
 
 
Section 1.1. 1.4, 1.9
Section 1.2. 1.12, 1.16, 1.19, 
Section 1.3. 1.24, 1.25
Section 1.4. 1.33
Section 2.1. 2.1, 2,2, 2.3, 2.6, 2.7, 2.9, 2.11
Section 2.2. 2.20, 2.22, 2.26, 2.27
 
 
These are the problems for Hw2.
 
Section 2.3. 2.31, 2.32, 2.34, 2.36
Section 2.4. 2.37, 2.39
Section 3.1. 3.4, 3.10
Section 3.4. 3.34 
Section 4.1. 4.2, 4.4
Section 4.2. 4.8, 4.10, 4.14, 4.16, 4.18, 4.23
Section 4.3. 4.28, 4.29 
Section 4.4. 4.34 
 

Extra notes

Please click here to find notes (from the book “Bondy J., Murty U. - Graph Theory With Applications, North Holland ed.”) on Dijkstra’s shortest path algorithm that I will present tomorrow. Click here for an example of application

Tests

The second test is on Thursday, Oct.29. A review sheet with extra problems is below.

E-mail

FIU is using an unpredictable SPAM filter which  quarantines  all kind of messages.
Make sure to you check your junk mail folder regularly because you may loose important e-mail.  It is advisable that you send me e-mail from your FIU address because of the SPAM   filter.  Keep in mind that   I always reply to e-mail  ... when I get it, of course!

A review sheet for Test3

A review sheet for Test2

A review sheet for Test1

The syllabus 

Back to my home page.