4.24 out of 5
4.24
271 reviews on Udemy

# Graph Theory

Master the Nuts and Bolts of Graph Theory: the Heart of Communication and Transportation Networks, Internet, GPS, ...
Instructor:
Miran Fattah
2,087 students enrolled
English [Auto-generated]
Master fundamental concepts in Graph Theory
Get to know a wide range of different Graphs, and their properties.
Be able to preform Elementary, Advanced Operations on Graphs to produce a new Graph
Understand Graph Coloring.
Understand Eulerian and Hamiltonian paths and circuits. And many related topics to Paths.
Know how to turn a Graph into a Matrix and vice versa.
Obtain a solid foundation in Trees, Tree Traversals, and Expression Trees.
Have a good understanding of Graph Match.

What is this course about?

Graph Theory is an advanced topic in Mathematics. On a university level, this topic is taken by senior students majoring in Mathematics or Computer Science; however, this course will offer you the opportunity to obtain a solid foundation in Graph Theory in a very short period of time, AND without requiring you to have any advanced Mathematical background.

You don’t need to know complex Mathematical statements, or rules, but ALL you need to know is simple mathematical operations like addition and multiplication. The course is designed to be understood by an 11th grader since the structure of the course starts with the very basic idea of how to create a Graph, and with each step the ideas get more and more complex. The structure of the course goes as following starting with the first section:

1. Graphs: In this section you will learn basic definitions like Vertex, Edge, Distance,                            Contentedness, and many other concepts that are the alphabet of Graph                          Theory.
2. Types of Graphs: In this section you will learn a variety of different Graphs, and their                       properties.
3. Graph Operations: In this section you will learn different operations and different                             methods in making new Graphs.
4. Graph Coloring: in this section you will learn Graph Coloring and many related                                 concepts.
5. Paths: in this lecture you will learn Euler and Hamiltonian Paths and Circuits, and                             many other concepts in that area.
6. Trees: In this section you will learn about Trees, Tree Traversals, Binary Expression                         Trees and some more.
7. And Graph Match: In this section you will about Graph Match and Graph Cover.

How are the concepts delivered?

Each lecture is devoted to explaining a concept or multiples concepts related to the topic of that section. There are example(s) after the explanation(s) so you understand the material more. The course is taught in plain English, away from cloudy, complicated mathematical jargons and that is to help the student learn the material rather than getting stuck with fancy words.

How to learn better?

Take notes and repeat the lectures to comprehend the concepts more. Also, there are quizzes every 3-5 lectures so you can test what you have learned and go over something if needed.

1
Introduction

### Graphs

1
Graphs

In this lecture we will define Graphs, Vertices, Edges, Degree of a Vertex, Degree Sequence, Graph Order, and Graph Size. And we will get to know the importance of Graphs.

2
Subgraphs

In this lecture we will get to know Subgraphs, and we will define Vertex Set and Edge Set.

3
Quiz
4
Graph Isomorphism

In this lecture we will explore Graph Isomorphism and its conditions.

5
Graph Automorphism
6
Quiz
7
Complement Graph

In this lecture we will talk about Complement Graphs, and what it means for Vertices to be adjacent.

8
Multigraphs

In this lecture we will talk about what it means for two Vertices to be connected by more than one Edge.

9
Quiz
10
Matrix Representation

In this lecture we will talk about Adjacency Matrix and Incidence Matrix.

11
Quiz
12
Walks, Trails and Paths

In this lecture we will define Walks, Trails, and Paths, and the difference between them. Also, we will talk about Self Avoiding Paths (SAP).

13
Distance

In this lecture we will talk about how Distance is measured in Graphs.

14
Connectedness

In this lecture we will talk about Graph Connectedness, Cut Edge, Cut Vertex, and Separating Sets.

15
Quiz
16
Menger's theorem
17
Sum of Degrees of Vertices Theorem

### Graph Types

1
Introduction
2
Null, Trivial, and Simple Graphs

In this lecture we will define Null, Trivial, Simple Graphs, Loops, and Parallel Edges.

3
Regular, Complete and Weighted Graphs
4
Directed, Undirected and Mixed Graphs

In this lecture we will define Directed Graphs, Indegree, Outdgree, a Source, and a Sink, and we will learn how we can do Adjacency Matrix for a Directed Graph. We will also talk about Undirected, and Mixed Graphs.

5
Quiz
6
Cycle, Path, Wheel and Lolipop Graphs

In this lecture we will learn the difference between Cycle Graphs, and a Cycle in a Graph. We will also define Girth of a Graph, Path Graphs, Wheel Graphs, and Lollipop Graphs.

7
Planar, Cubic and Random Graphs
8
ladder and Prism Graphs

In this lecture we will talk about Ladder and Prism Graphs, and how we can count the number of the Edges in each.

9
Web and Signed Graphs

In this lecture we will define Web and Signed Graphs, and we will get to know a psychologist's contribution to Graph Theory.

10
Quiz
11
Peterson Graph
12
Bipartite Graphs
13
Platonic Graphs

The illustrations shown in this lecture are NOT owned by the instructor of this course. To reach the website containing the illustrations, follow this link : https://www.learner.org/interactives/geometry/platonic.html

### Graph Operations

1
Introduction
2
Vertex Addition and Deletion
3
Edge Addition and Deletion
4
Vertex Contraction and Edge Contraction
5
Quiz
6
Graph Minor and Graph Transpose
7
Line Graphs

In this lecture we will talk about Line Graphs which, and the process of creating them.

8
Dual Graphs

In this lecture we will talk about the process of creating a Dual Graph from another Graph.

9
Graph Power

In this lecture, we will talk about how to find the k^th Power of a Graph.

10
Y - Δ Transform
11
Quiz
12
Graph Join and Graph Product

In the lecture we will talk about the process of Joining and the steps that go into the Cartesian Product of two Graphs.

In Cartesian Product of two graphs, I mention the word "multiply" which in this context means "Product" or "Cartesian Product".

13
Hajós Construction
14
Graph Union and Graph Intersection

In this lecture we will talk about how we can create a new Graph by Union and Intersection of two Graphs.

15
Series - Parallel Composition
16
Quiz

### Graph Coloring

1
Introduction
2
Vertex Coloring

In this lecture we will define Vertex Coloring, Chromatic Number, k-Colorable Graphs, and Independent Sets.

3
Edge Coloring
4
Quiz
5
Chromatic Polynomial

In this lecture we will define Chromatic Polynomials and show you how to use the software to find the Chromatic Polynomial of any Graph. Here is the link to Bob Weaver's website: http://www.mtholyoke.edu/~bweaver/vita/software.htm

6
Total and List Coloring
7
Exact and Fractional Coloring
8
Rainbow Coloring
9
Vizing's Theorem

In this lecture we will talk about Vizing's Theorem and Maximum Degree.

10
Four Color Theorem

### Paths

1
Introduction
2
The Königsberg Bridge Problem

In this lecture we will talk about what triggered Graph Theory.

3
Euler Paths and Circuits

In this lecture we will define Euler Paths and Euler Circuits, and we will see why there isn't a solution to the Königsberg Bridge Problem.

4
Fleury’s Algorithm

In this lecture we will talk about Fleury's way of finding an Euler Path or Circuit.

5
Hierholzer's Algorithm
6
Quiz
7
Hamiltonian Paths and Circuits

In this lecture we will define Hamiltonian Paths and Circuits.

8
Hamiltonian Decomposition

In this lecture we will explore decomposing a Graph based on the Hamiltonian Circuits in it.

9
Ore's Theorem
10
Dirac's Theorem
11
Quiz
12
Shortest Path Problem

In this lecture we will see how we can find the shortest path in a Graph using Dijkstra's Algorithm.

13
Five Room Puzzle
14
Knight's Tour

### Trees

1
Introduction
2
Trees

In this lecture we will define Trees, their properties, their importance in Computer Science, and how we can count them using Cayley's Formula.

3
Tree Types

In this lecture we will talk about Star Trees, Caterpillar Trees, Lobster Trees, and Banana Trees.

4
Rooted Trees

In this lecture we will define Rooted Trees, Out Tree, In Tree, Parent, Child, Sibling, Ancestor, Descendant, Uncle, Leaf, Internal and External Vertices, Subtree, Levels, Height, and Depth.

5
Tree Structures

In this lecture, we will talk about different ways we can represent a Tree visually.

6
Quiz
7
Binary Trees

In this lecture we will talk about Binary Trees, and its different types (Proper, Perfect, Complete, Infinite Complete, and Balanced Binary Trees).

8
Spanning Trees
9
Quiz
10
Binary Expression Trees

In this lecture you will learn how to convert an Algebraic or Boolean expression into a Tree and vice versa.

11
Tree Traversal

In this lecture we will talk about Preorder, Inorder, Postorder, and Levelorder Tree Traversals. To practice more, go to below website and you will find numerous practice examples at the very end of the page.

http://algoviz.org/OpenDSA/Books/OpenDSA/html/BinaryTreeTraversal.html

12
Quiz
13
Forests

### Graph Match

1
Introduction
2
Graph Match

In this lecture we will get to know Matching, Maximum and Maximal Matching, Perfect Matching, and Near Perfect Matching.

3
Hosoya Index
4
Berge's Lemma

In this lecture, beside talking about Berge's Lemma, we will talk about Augmenting Paths, and Alternating Paths.

5
Vertex and Edge Cover
6
König's Theorem

In this lecture we will see the relationship between Matching and Vertex Cover for Bipartite Graphs.

7
Quiz
8
Bonus Lecture
You can view and review the lecture materials indefinitely, like an on-demand channel.
Definitely! If you have an internet connection, courses on Udemy are available on any device at any time. If you don't have an internet connection, some instructors also let their students download course lectures. That's up to the instructor though, so make sure you get on their good side!
4.2
4.2 out of 5
271 Ratings

#### Detailed Rating

 Stars 5 128 Stars 4 99 Stars 3 31 Stars 2 8 Stars 1 3
30-Day Money-Back Guarantee

#### Includes

6 hours on-demand video
Full lifetime access
Access on mobile and TV
Certificate of Completion