Official government website of the Government of Kingdom of Saudi Arabia
Link to official Saudi websites end with edu.sa

All links to official educational websites in the Kingdom of Saudi Arabia end with sch.sa or edu.sa

Government websites use the HTTPS protocol for encryption and security.

Secure websites in the Kingdom of Saudi Arabia use the HTTPS protocol for encryption.

Registered with the Digital Government Authority under number:

20250417892
Main
UQU Programs
Mathematics

Graph Theory

MTH3204
3 hours English

Graph Theory

Graph Theory
MTH2203 Combinatorics
3 hours Two requisites
1 Introduction to Graph Theory and Graph Models: Basic definitions of graph terminology (vertices, edges, degree), and special types of graphs (directed, undirected, weighted, simple)
2 Representing Graphs and Graph Isomorphism: Definitions, examples, adjacency matrices for graph representation
3 Connectivity and Shortest-Path Problems
4 Euler Walks, and Circuits: Definitions, properties, and applications of walks, trails, paths, and Euler circuits in directed and undirected graphs
5 Hamilton Cycles and Hamiltonian Graphs: / Introduction to Hamilton cycles, differences from Eulerian graphs, examples and applications
6 Planar Graphs, Euler's Formula, and Homeomorphism: / Definitions, planarity testing, applications, Euler's formula, and the concept of homeomorphism
7 Graph Coloring: Definition, properties, real-life examples, and applications in graph coloring, scheduling
8 Trees: Definition, properties, spanning trees, minimum spanning trees, applications of trees in graph theory
9 Maps and Dual Graphs: / Maps as graphs, definition, and examples of dual graphs with some applications
10 Others: Revision and activities, Exam, quizzes
1.1 Mapped to: K1, K2

Understand and apply the basic concepts of graph theory, including vertices, edges, degrees, and various types of graphs such as directed, undirected, weighted, and simple graphs.

Teaching Strategy Lectures
Assessment Methods Homework, periodic and final exams
1.2 Mapped to: K1, K2

Represent and manipulate graphs using matrices and other graph representations

Teaching Strategy Lectures
Assessment Methods Homework, periodic and final exams
2.1 Mapped to: S1, S2

Apply and using advanced techniques such as isomorphic graphs, adjacency matrices, spanning trees, Eulerian and Hamiltonian cycles, and coloring algorithms to solve graph-related problems.

Teaching Strategy Lectures
Assessment Methods Homework, periodic and final exams
2.3 Mapped to: S5, S6

Apply graph theory concepts to develop mathematical proofs to prove real-world problems, such as scheduling, planning, and map coloring.

Teaching Strategy Lectures
Assessment Methods Homework, periodic and final exams
3.1 Mapped to: V1

Demonstrate the ability to independently apply graph theory concepts to solve complex problems and develop innovative solutions.

Teaching Strategy Lectures
Assessment Methods Homework, periodic and final exams
Assessment
Weight
Med term exam
30%
Homework and assignments
20%
Final Exam
50%
Total
100%