20295 Graph Theory
Credits: 4 intermediate credits in Mathematics
Prerequisites: none
Required: Linear Algebra I, having accumulated a total of at least 24 credits in Mathematics, as well as the ability to read scientific texts in English
Recommended: Basic knowledge of combinatorics, which can be acquired from one of the following: Discrete Mathematics: Set Theory, Combinatorics and Graph Theory,1 or Introduction to Statistics and Probability for Science Students, or Probability for Computer Science Students, or Probability Theory
The course, based on chapters 1-11 of Graph Theory with Applications, by J.A. Bondy and U.S.R. Murty (North Holland, 1976), was developed by Abraham Ginzburg and Nur Arad.
Graph theory is a field of mathematics that has many applications in Computer Science and in various fields of mathematics. The basic concepts of this theory are easy to understand and do not require much mathematical background. Considerable amount of mathematical experience and sophistication is required, however, to grasp the theory that connects the various basic concepts to each other.
The course, which is primarily intended for Mathematics and Computer Science students, may also interest students of other disciplines who have mathematical inclinations. The students study Chapters 1-11 of the course book (in English) using a comprehensive study guide (in Hebrew).
The emphasis in this course is on the mathematical theory of graph theory. Alongside the theorems and their proofs that go into great mathematical depth, the book presents a variety of applications of graph theory, among them algorithms of graph theory that have important uses in Computer Science. The applications demonstrate how the mathematical theory can be used to solve problems that are otherwise difficult or impossible to solve.
Topics: Graphs and subgraphs; Trees; Connectivity; Euler tours and Hamilton cycles; Matchings; Edge colorings; Independent sets and cliques; Vertex colorings; Planar graphs; Directed graphs; Networks.
1or Discrete Mathematics: Set Theory, Combinatorics and Logic (20283), which is no longer offered.