Graph Theory Lecture Notes

← Back to document page

Graph Theory : Penn State Math 485 LectureNotesVersion Griffin 2011-2021Licensed under a Creative Commons Attribution-Noncommercial-Share Alike United States LicenseWith Contributions By:Elena KosyginaSuraj ShekharContentsList of FiguresvPrefacexiChapter 1. Introduction to Graph Theory11. An Overview of Graph Theory12. Graphs, Multi-Graphs, Simple Graphs23. Directed Graphs74. Elementary Graph Properties: Degrees and Degree Sequences95. Subgraphs146. Graph Complement, Cliques and Independent Sets15Chapter 2. More Definitions and Theorems191. Paths, Walks, and Cycles192. More Graph Properties: Diameter, Radius, Circumference, Girth213. More on Trails and Cycles224. Graph Components235. Introduction to Centrality286. Bipartite Graphs297.

3.11 This graph has negative edge weights that lead to confusion in Dijkstra’s Algorithm55 3.12 The steps of Dijkstra’s algorithm run on the graph in Figure3.11.56 3.13 A negative cycle in a (directed) graph implies there is no shortest path between any two vertices as repeatedly going around the cycle will make the path smaller and smaller.57

  Weight