Introduction to Graph Theory
Join the programme by Coursera to learn how to pictorially represent mathematical results easily and provide knowledge of the theories behind them.
Beginner
Online
5 Weeks
13,514 INR Quick Facts
| Medium Of Instructions | Mode Of Learning | Mode Of Delivery |
|---|---|---|
| English | Self Study | Video and Text Based |
Course Overview
Taking the Introduction to Graph Theory certification course will provide you with useful insights into how engineers design integrated circuits and how GPS systems find shortest routes. You will also learn why a political map can only be coloured using a few colours and how biologists assemble genomes. The course curriculum includes the Ramsey Theory, which proves that complete disorder is impossible in an extensive system.
Additionally, the curriculum for the Introduction to Graph Theory certification course will cover a wide variety of graphs, including Airlines Graphs, Directed Graphs, Bipartite Graphs, and more. You will become adept in applying various algorithms to solve real-world problems via practice exercises and hands-on projects.
Moreover, National Research University Higher School of Economics and the University of California and San Diego are offering the Introduction to Graph Theory programme jointly. As a result, candidates will be able to find better career opportunities upon course completion.
The Introduction to Graph Theory online course is highly suitable for professionals working in the IT sector and IT aspirants.
The Highlights
- Flexible deadlines
- 100% online
- Self-paced learning option
- Graded quizzes and assignments
- Beginner level
- Lessons in English
- Peer feedback
- Approximately 20 hours of learning
- Shareable certificate
Programme Offerings
- 100% online learning
- Beginner-level Course
- Approximately 20 hours long
- Shareable Certificate
- Flexible Deadlines
- Graded Quizzes
- peer feedback
Courses and Certificate Fees
| Certificate Availability | Certificate Providing Authority |
|---|---|
| yes | UC San DiegoCoursera |
Introduction to Graph Theory Certification Course Fee Structure :
| Fees components | Amount |
| 1 month | Rs. 6,757 |
| 3 month | Rs. 13,514 |
| 6 month | Rs. 20,271 |
Eligibility Criteria
Candidates applying for the Introduction to Graph Theory certification programme should have a basic understanding of math and elementary programming proficiency in python.
What you will learn
The Introduction to Graph Theory certification course will introduce you to diverse topics in Graph theory via course videos, readings, and practice exercises. Upon course completion, you will be adept in:
- Defining a Graph
- Finding the right ordering of a project dependency graph
- Differentiate between Eulerian and Hamiltonian cycles
- Defining minimum spanning trees
- Defining graph colourings
- Proving Ramsey Theorem
- Finding the minimum number of computers to control all network connections
- Develop an algorithm which helps in matching students with schools, doctors with hospitals, and organ donors with patients
Who it is for
People who work or intend to work in IT can apply for the Introduction to Graph Theory course by Coursera.
Admission Details
You can apply for admission to the Introduction to Graph Theory certification programme by following these steps:
- Visit the course page.
- Log in to the “Introduction to Graph Theory” course page using the catalogue of Coursera.
- Click on the “Enroll for Free” button on the page.
- The system will prompt you to either audit the course for free or subscribe for the paid course. You can also opt for a 7-day free trial before purchasing the certification course.
- Once you choose the paid subscription, the browser will direct you to a payment gateway.
- Make the payment and you are done.
Application Details
You can enrol in the programme by simply logging into the course page on the website of Coursera. You can do so using your Google or email account. Finally, you need to choose the learning option and to pay the fee and complete the enrollment process.
The Syllabus
Videos
- 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
Readings
- Slides
- Slides
- Slides
- Slides
- Glossary
- Hint for Guarini's Puzzle
Assignments
- Puzzle: Make a tree
- Puzzle: Guarini's Puzzle
- Puzzle: Bridges of Königsberg
- Definitions
- Graph Types
Ungraded lab
- Graph Drawing Example
Videos
- 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
Readings
- Slides
- Slides
- Slides
- Glossary
Assignments
- 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
Ungraded labs
- Connected Components
- Guarini Puzzle Solver
- Topological Sorting
- Strongly Connected Components
- Eulerian Cycles
Videos
- 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
Readings
- Slides
- Slides
- Slides
- Glossary
Assignments
- Puzzle: Road Repair
- Trees
- Puzzle: Job Assignment
- Bipartite Graphs
- Puzzle: Subway Lines
- Planar Graphs
Ungraded labs
- Minimum Spanning Tree
- Maximum Matching
Videos
- 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
Readings
- Slides
- Slides
- Slides
- Slides
- Glossary
Assignments
- Puzzle: Map Coloring
- Graph Coloring
- Puzzle: Graph Cliques
- Cliques and Independent Sets
- Puzzle: Balanced Graphs
- Ramsey Numbers
- Puzzle: Antivirus System
- Vertex Covers
Ungraded lab
- Maximum Clique
Videos
- 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
Readings
- Slides
- Slides
- The algorithm and its properties (alternative exposition)
- Gale-Shapley Algorithm
- Project Description
- Glossary
Assignments
- Constant Degree Bipartite Graphs
- Algorithm
- Choose an Augmenting Path Carefully
- Base Cases
Instructors
UC San Diego Frequently Asked Questions (FAQ's)
Candidates can either opt for a free audit or the paid subscription. The free audit does not include graded assessments or the certificate, for which you will have to pay the course fee.
To apply, click on the “financial aid available” tab that is next to the “Enroll for Free” button on the course page.
You can learn more about this course by clicking on the “Learner Help Center” link at the bottom of the course page on Coursera’s official website.
Yes, students will receive a combined certificate from the National Research University Higher School of Economics, University of California San Diego, and Coursera.