Matematica | GRAPH THEORY

cod. 0512300028

GRAPH THEORY

	0512300028
	DIPARTIMENTO DI MATEMATICA
	EQF6
	MATHEMATICS
	2020/2021

PERCORSO SHARED STUDY PATHWAY

	YEAR OF COURSE 3
	YEAR OF DIDACTIC SYSTEM 2018
	PRIMO SEMESTRE

TEACHING UNITS

	SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
	MAT/03	6	48	LESSONS	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS

	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.

- 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

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: T. HARJU, GRAPH THEORY, LECTURE NOTES (2012, DOWNLOADABLE FROM THE WEB) 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

Texts

TEXTBOOKS:

T. HARJU, GRAPH THEORY, LECTURE NOTES (2012, DOWNLOADABLE FROM THE WEB)

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