Course Summary
Learn about graph theory and its applications in computer science and data science. This course covers topics like graph representation, traversal, shortest path algorithms, and more.Key Learning Points
- Understand the basics of graph theory and its applications
- Implement graph algorithms in Python
- Apply graph theory in real-world scenarios
Related Topics for further study
Learning Outcomes
- Develop a solid understanding of graph theory and its applications
- Be able to implement graph algorithms in Python
- Use graph theory to solve real-world problems
Prerequisites or good to have knowledge before taking this course
- Basic knowledge of Python programming
- Familiarity with data structures and algorithms
Course Difficulty Level
IntermediateCourse Format
- Online
- Self-paced
Similar Courses
- Data Structures and Algorithms
- Applied Data Science with Python
Notable People in This Field
- Donald Knuth
- Tim Berners-Lee
Related Books
Description
We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them.
Outline
- What is a Graph?
- Airlines Graph
- Knight Transposition
- Seven Bridges of Königsberg
- What is a Graph?
- Graph Examples
- Graph Applications
- Vertex Degree
- Paths
- Connectivity
- Directed Graphs
- Weighted Graphs
- Paths, Cycles and Complete Graphs
- Trees
- Bipartite Graphs
- Slides
- Slides
- Slides
- Slides
- Glossary
- Hint for Guarini's Puzzle
- Puzzle: Guarini's Puzzle
- Puzzle: Bridges of Königsberg
- Definitions
- Puzzle: Make a tree
- Graph Types
- CYCLES
- Handshaking Lemma
- Total Degree
- Connected Components
- Guarini Puzzle: Code
- Lower Bound
- The Heaviest Stone
- Directed Acyclic Graphs
- Strongly Connected Components
- Eulerian Cycles
- Eulerian Cycles: Criteria
- Hamiltonian Cycles
- Genome Assembly
- Slides
- Slides
- Slides
- Glossary
- Puzzle: Connect Points by Segments
- Computing the Number of Edges
- Number of Connected Components
- Number of Strongly Connected Components
- Eulerian Cycles
- Puzzle: Plow Truck
- Puzzle: Hamiltonian Cycle
- Graph Classes
- Road Repair
- Trees
- Minimum Spanning Tree
- Job Assignment
- Bipartite Graphs
- Matchings
- Hall's Theorem
- Subway Lines
- Planar Graphs
- Euler's Formula
- Applications of Euler's Formula
- Slides
- Slides
- Slides
- Glossary
- Puzzle: Road Repair
- Trees
- Puzzle: Job Assignment
- Bipartite Graphs
- Puzzle: Subway Lines
- Planar Graphs
- Graph Parameters
- Map Coloring
- Graph Coloring
- Bounds on the Chromatic Number
- Applications
- Graph Cliques
- Cliques and Independent Sets
- Connections to Coloring
- Mantel's Theorem
- Balanced Graphs
- Ramsey Numbers
- Existence of Ramsey Numbers
- Antivirus System
- Vertex Covers
- König's Theorem
- Slides
- Slides
- Slides
- Slides
- Glossary
- Puzzle: Map Coloring
- Graph Coloring
- Puzzle: Graph Cliques
- Cliques and Independent Sets
- Puzzle: Balanced Graphs
- Ramsey Numbers
- Puzzle: Antivirus System
- Vertex Covers
- Flows and Matchings
- An Example
- The Framework
- Ford and Fulkerson: Proof
- Hall's theorem
- What Else?
- Why Stable Matchings?
- Mathematics and Real Life
- Basic Examples
- Looking For a Stable Matching
- Gale-Shapley Algorithm
- Correctness Proof
- Why The Algorithm Is Unfair
- Why the Algorithm is Very Unfair
- Slides
- Slides
- The algorithm and its properties (alternative exposition)
- Gale-Shapley Algorithm
- Project Description
- Glossary
- Choose an Augmenting Path Carefully
- Constant Degree Bipartite Graphs
- Base Cases
- Algorithm
Summary of User Reviews
Discover the world of Graph Theory and learn to solve complex problems using graphs. Students rate this course highly for its in-depth coverage of the topic and engaging course materials.Key Aspect Users Liked About This Course
Many users appreciated the practical applications of Graph Theory covered in the course.Pros from User Reviews
- In-depth coverage of Graph Theory topics
- Engaging course materials, including interactive quizzes and assignments
- Practical applications of Graph Theory covered in the course
- Excellent instructors who are knowledgeable and responsive to student questions
- Flexible pacing allows students to learn at their own pace
Cons from User Reviews
- Some users found the course challenging and required additional outside resources to fully understand the material
- The course is heavily focused on theoretical concepts and may not be as applicable to real-world situations
- Some users found the quizzes and assignments to be too difficult and time-consuming
- Limited opportunity for interaction with other students in the course
- No certificate or credential offered upon completion of the course
Alexander S. Kulikov
4.5 Raiting
From Freedom Rides to Ferguson: Narratives of Nonviolence in the American Civil Rights Movement
- 4.8
-
![]()
![]()
![]()
![]()
![]()
The Modern Civil Rights Movement is a significant landmark in United States history. Bernard LaFayette, Jr. The course hosts several guest speakers, including Andrew Young, Reverend C....
Financial Engineering & Portfolio Theory -CM2 Actuarial Exam
- 4.4
-
![]()
![]()
![]()
![]()
![]()
By MJ the Fellow Actuary Section 1 - Introduction Financial Markets Efficient Market Hypothesis Can you Beat the Market? Active vs Passive Strategies...
Artificial Intelligence Data Fairness and Bias
- 4.9
-
![]()
![]()
![]()
![]()
![]()
In this course, we will explore fundamental issues of fairness and bias in machine learning. Fairness and protections in machine learning...
Nuclear Reactor Physics Basics
- 4.4
-
![]()
![]()
![]()
![]()
![]()
This engineering course is designed to introduce students to a range of concepts, ideas and models used in nuclear reactor physics....
