Directed and undirected graphs, representations, classification, isomorphism, connectivity, Euler and Hamilton paths, shortest paths, planarity, coloring, application to computer networks.
Section 10.1-10.8: Graphs, terminology, representations, connectivity, Euler and Hamilton paths, shortest paths, planar graphs, coloring
Textbook 94 pages
Directed graphs, undirected graphs, representation of graphs, classification of undirected graphs.
Lecture notes
Graph traversal: DFS and BFS, connectivity, graph isomorphism.
Euler paths, Hamilton paths, planarity, coloring, miscellaneous terminology.
Shortest paths, a key idea of Dijkstra’s algorithm: the greedy method, a key idea of Floyd’s Algorithm: dynamic programming.
Niche overlap graphs, influence graphs (Rosen Section 10.1)
Problems
Solutions
Vertices, edges, degree, neighborhood, bipartite, union (Rosen Section 10.2)
Adjacency lists, adjacency matrices, undirected graphs, incidence matrices, isomorphism (Rosen Section 10.3)
Simple paths, circuits, lengths, strongly and weakly connected graphs and components (Rosen Section 10.4)
Determining Euler and Hamilton circuits, Dirac’s theorem, Ore’s theorem (Rosen Section 10.5)
Finding lengths and shortest paths (Rosen Section 10.6)
Recognizing and manipulating planar graphs (Rosen Section 10.7)
Constructing dual graphs, finding chromatic numbers (Rosen Section 10.8)