Graph Theory - USTH - 2024

Session 1 - Introduction

• Slides: Introduction to graphs
• Code: naïve Graph class using edge adjacency lists basic_graph_adjlist.py
• Code: naïve Graph class using adjacency matrix basic_graph_matrix.py
• Notebook: plotting a graph with matplotlib
• Notebook: Introduction to NetworkX
• Notebook: Plotting Karate Network using NetworkX

Graph Software

• Gephi: The Open Graph Viz Platform
• Video tutorial: Introduction to Network Analysis and Visualization

Session 2 - ADT - Graph Traversal - Complexity

• Slides: Abstract Data Types: Stacks, Queues, and Dictionaries

• Slides: Graph Traversal Algorithms, DFS
• Notebook: A simple python implementation of DFS using recursion 02-a-DFS-recursive.ipynb
• Code: copy lib directory and its content lib
• Data: example graph: copy soc-karate.mtx
• Slides: DFS Algorithm with a stack

Session 3 - Graph Traversal - Complexity

• Slides: Algorithmic Complexity
• Slides: Breadth-First-Search (BFS)
• Slides Dijkstra's Algorithm

Session 4 - Minimum Spanning Tree

• Slides: Prim's and Kruskal algorithms
• Slides: Minimum Spanning Tree: examples

Session 5 - Binary Trees - Huffman - Binary Search Trees

• Slides: Binary Trees - Huffman - Binary Search Trees

Session 6 - Maximum flows - Ford-Fulkerson - Edmonds and Karp

• Slides: Maximum Flows

Session 7 - Graph Coloring

• Slides: Graph Coloring

Session 8 - Introduction to NP-complete problems

• Slides: Intro. NP-complete

Session 9 - Complex Networks

• Slides: Complex Networks

References (textbooks)

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms (2nd edition), The MIT Press, 2001.
2. David Joyner, Minh Van Nguyen, and Nathann Cohen, Algorithmic Graph Theory, 2010.
3. Anany Levitin, Introduction to The Design & Analysis of Algorithms, Pearson, 2011
4. Douglas B. West, Introduction to Graph Theory, Prentice Hall, 1996
5. Gary Chartrand, Ping Zhang, A First Course in Graph Theory (Dover Books on Mathematics) Illustrated Edition, 2012.
6. Maarten van Steen, Graph Theory and Complex Networks: An Introduction, 2010.
7. Albert-László Barabási, Márton Pósfai, Network Science 1st Edition, 2016