# Matematica | GRAPH THEORY

## Matematica GRAPH THEORY

 0512300028 DIPARTIMENTO DI MATEMATICA EQF6 MATHEMATICS 2020/2021

 YEAR OF COURSE 3 YEAR OF DIDACTIC SYSTEM 2018 PRIMO SEMESTRE
SSD CFU HOURS ACTIVITY TYPE OF ACTIVITY MAT/03 6 48 LESSONS COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS
 FABRIZIO PUGLIESE T
Objectives
- KNOWLEDGE AND UNDERSTANDING: THE AIM OF THE COURSE IS TO TEACH THE BASIC NOTIONS OF GRAPH THEORY, TO SHOW ITS RELATIONS WITH OTHER FIELDS OF MATHEMATICS AND TO GIVE SOME EXAMPLES OF ITS INNUMERABLE PRACTICAL APPLICATIONS. THE COURSE WILL GIVE THE STUDENT THE OCCASION TO: LEARN SOME FUNDAMENTAL TOOLS OF COMBINATORIAL ANALYSIS AND SEE SOME SURPRISING APPLICATIONS OF LINEAR ALGEBRA TO THE STUDY OF THE STRUCTURE OF GRAPHS;

- APPLYING KNOWLEDGE AND UNDERSTANDING: ONE OF THE MAIN AIMS OF THE COURSE IS TO GIVE STUDENTS THE ABILITY TO PRACTICALLY APPLY THE THEORETICAL NOTIONS AND COMPUTATIONAL TOOLS THEY WILL LEARN. TO THIS AIM, MANY LECTURES WILL BE DEVOTED TO PROBLEM SESSIONS, IN WICH IT WILL BE SHOWN HOT TO SUCCESFULLY APPLY GRAPH THEORY TO CONCRETE PROBLEMS SUCH AS: OPTIMIZATION, NETWORK ANALYSIS, SEARCH ALGORITHMS, ETC.
Prerequisites
THE ONLY NEEDED PRELIMINARY KNOWLEDGES ARE THE BASIC ONES IN LINEAR ALGEBRA AND ABSTRACT ALGEBRA USUALLY GIVEN IN THE STANDARD UNDERGRADUATE COURSES.
Contents
1. BASIC NOTIONS.

VARIOUS KINDS OF GRAPHS. GRAPH OPERATIONS. GRAPH ISOMORPHISMS. WALKS,PATHS AND CYCLES; DISTANCE, GEODESICS, DIAMETER, GIRTH.

2. CONNECTIVITY.

TREES AND FORESTS; BIPARTITE GRAPHS. ALGORITHMS ON SPANNING TREES (BREADTH-FIRST, SEARCH-FIRST; DIJKSTRA; KRUSKAL). SEPARATING SETS AND CONNECTIVITY; WHITNEY'S INEQUALITY. MENGER THEOREM.

3. EULERIAN AND HAMILTONIAN GRAPHS.

EULERIAN CIRCUITS AND EULER'S THEOREM. CHINESE POSTMAN PROBLEM, FLEURY'S ALGORITHM. HAMILTONIAN CYCLES; ORE THEOREM; CLOSURE OF A GRAPH; CHVATAL THEOREM.

4. MATCHINGS.

MATCHINGS AND VERTEX COVERS; MAXIMUM MATCHINGS; BERGE THEOREM. MATCHINGS IN BIPARTITE GRAPHS; HALL THEOREM, KOENIG THEOREM, TUTTE THEOREM. STABLE MARRIAGES, GALE-SHAPLEY ALGORITHM.

5. NETWORKS AND FLOWS.

FLOWS IN A NETWORK; MAX FLOW-MIN CUT THEOREM, FORD-FULKERSON ALGORITHM, EDMONDS-KARP ALGORITHM; INTEGRAL FLOWS; EQUIVALENCE OF MF=MC, HALL AND MENGER THEOREMS

6. GRAPHS EMBEDDED IN SURFACES.

PLANAR GRAPHS; EULER FORMULA AND ITS CONSEQUENCES; KURATOWSKI'S THEOREM; DEMOUCRON'S PLANARITY TEST. GRAPH GENUS; EMBEDDINGS OF K_5 AND K_3,3 INTO THE TORUS.

7. (VERTEX- AND EDGE- )COLORINGS; CHROMATIC NUMBER AND ITS ESTIMATES (GREEDY ALGORITHM, BROOK'S AND VIZING'S THEOREMS). 5 COLORS THEOREM; SOME HINTS ON 4 COLORS THEOREM. GRAPH HOMOMORPHISMS; HOM-EQUIVALENCE AND CORES.

8. ALGEBRAIC GRAPH THEORY.

ADJACENCY, ORIENTED INCIDENCE AND LAPLACIAN OPERATORS; FLOW SPACE AND CUT SPACE; MATRIX-TREE THEOREM

Teaching Methods
ABOUT 2/3 OF THE COURSE WILL BE DEVOTED TO FRONTAL LECTURES AND ABOUT 1/3 TO PRACTICAL CLASSES, DURING WHICH VARIUOS EXERCICES AND PROBLEMS WILL BE DONE, WHILE OTHERS WILL BE ASSIGNED AS HOMEWORK, SO THAT STUDENTS CAN DEVELOP THEIR ABILITY TO SOLVE PROBLEMS AUTONOMOUSLY.
Verification of learning
THE AIM OF THE FINAL TEST IS TO VERIFY BOTH THE STUDENT'S KNOWLEDGE OF THE THEORY AND HIS/HER ABILITY TO APPLY IT TO THE SOLUTION OF CONCRETE PROBLEMS. THE EXAM, WHICH WILL TAKE PLACE IN ONE SESSION, WILL BE DIVIDED IN:

1. THE ORAL DISCUSSION OF HOMEWORK

2. THE SOLUTION OF A SIMPLE EXERCISE PROPOSED BY THE EXAMINER

3. AN INTERVIEW ON ONE OR TWO ITEMS OF THE PROGRAM, CHOSEN BY THE EXAMINER.
Texts
TEXTBOOKS:

B. BOLLOBAS: MODERN GRAPH THEORY (GTM 184, SPRINGER, 1998)

C. GODSIL, G.F. ROYLE: ALGEBRAIC GRAPH THEORY (GTM 207, SPRINGER, 2001)

NOTES BY THE INSTRUCTOR

TEXTS FOR CONSULTING:

J.A. BONDY, U.S.R. MURTY, GRAPH THEORY (GTM SPRINGER, 2008)

R. DIESTEL: GRAPH THEORY (GTM SPRINGER, 2006)

N. BIGGS: ALGEBRAIC GRAPH THEORY (CAMBRIDGE UNIVERSITY PRESS, 1993)

D. WEST, INTRODUCTION TO GRAPH THEORY, PRENTICE HALL 2001