Matematica | GRAPH THEORY

cod. 0512300028

GRAPH THEORY

	0512300028
	DIPARTIMENTO DI MATEMATICA

	MATHEMATICS
	2013/2014

CURRICULUM MATEMATICA AD INDIRIZZO APPLICATIVO Cohort 2011/2012

	YEAR OF COURSE 3
	YEAR OF DIDACTIC SYSTEM 2010
	PRIMO SEMESTRE

TEACHING UNITS

	SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
	MAT/03	6	48	LESSONS	OPTIONAL SUBJECTS

	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 WHICH ARE NOT USUALLY TAUGHT IN OTHER UNDERGRADUATE COURSES; SEE SOME SURPRISING APPLICATIONS OF LINEAR ALGEBRA TO THE STUDY OF THE STRUCTURE OF GRAPHS; REALIZE HOW WIDE IS THE RANGE OF APPLICATIONS OF GRAPH THEORY IN OTHER FIELDS. THE PROGRAMME OF THE COURSE HAS BEEN PLANNED SO THAT THE STUDENTS GET AN ORGANIC AND COHERENT VIEW OF THE SUBJECT AND CAN EASILY SEE WHICH ARE THE FUNDAMENTAL IDEAS. - 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. - MAKING JUDGMENTS: ONE OF THE AIMS OF THE COURSE IS HELPING STUDENTS TO DEVELOP THEIR CRITICAL FACULTIES, SO THAT THEY WILL BE ABLE TO AUTONOMOUSLY JUDGE WHICH ARE THE REALLY IMPORTANT IDEAS AND WHICH SUBJECTS IT WOULD BE WORTHY FOR THEM TO SPECIALIZE IN. - COMMUNICATION SKILLS: THE STUDENT WILL BE GIVEN THE LINGUISTIC/MATHEMATICAL TOOLS ALLOWING HIM/HER TO CLEARLY AND RIGOROUSLY COMMUNICATE ADVANCED NOTIONS AND RESULTS OF GRAPH THEORY - LEARNING SKILLS: AMONG THE AIMS OF THE COURSE THERE IS THAT OF INCREASING THE STUDENTS' LEARNING SKILLS AND THEIR FLEXIBILITY IN COPING WITH APPLCATIONS WHICH, THOUGH THEY SEEM AT FIRST SIGHT TOTALLY UNRELATED WITH EACH OTHER, CAN IN FACT BE SOLVED USING THE SAME TOOLS AND IDEAS FROM GRAPH THEORY. FURTHERMORE, THE DETAILS SOME PROOF WILL BE LEFT TO THE STUDENTS AS A HOMEWORK EXERCISE, ESPECIALLY IN THOSE CASES IN WHICH A CERTAIN PROCEDURE OR IDEA HAS ALREADY BEEN USED IN PREVIOUS PROOFS; IN THIS WAY, STUDENTS WILL BE FORCES TO ABANDON THAT PASSIVE ATTITUDE IN THEIR STUDY HABITS WHICH IS OFTEN A SERIOUS OBSTACLE TO THE IMPROVEMENT OF THEIR LEARNING SKILLS

- 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 WHICH ARE NOT USUALLY TAUGHT IN OTHER UNDERGRADUATE COURSES; SEE SOME SURPRISING APPLICATIONS OF LINEAR ALGEBRA TO THE STUDY OF THE STRUCTURE OF GRAPHS; REALIZE HOW WIDE IS THE RANGE OF APPLICATIONS OF GRAPH THEORY IN OTHER FIELDS. THE PROGRAMME OF THE COURSE HAS BEEN PLANNED SO THAT THE STUDENTS GET AN ORGANIC AND COHERENT VIEW OF THE SUBJECT AND CAN EASILY SEE WHICH ARE THE FUNDAMENTAL IDEAS.

- 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.

- MAKING JUDGMENTS: ONE OF THE AIMS OF THE COURSE IS HELPING STUDENTS TO DEVELOP THEIR CRITICAL FACULTIES, SO THAT THEY WILL BE ABLE TO AUTONOMOUSLY JUDGE WHICH ARE THE REALLY IMPORTANT IDEAS AND WHICH SUBJECTS IT WOULD BE WORTHY FOR THEM TO SPECIALIZE IN.

- COMMUNICATION SKILLS: THE STUDENT WILL BE GIVEN THE LINGUISTIC/MATHEMATICAL TOOLS ALLOWING HIM/HER TO CLEARLY AND RIGOROUSLY COMMUNICATE ADVANCED NOTIONS AND RESULTS OF GRAPH THEORY

- LEARNING SKILLS: AMONG THE AIMS OF THE COURSE THERE IS THAT OF INCREASING THE STUDENTS' LEARNING SKILLS AND THEIR FLEXIBILITY IN COPING WITH APPLCATIONS WHICH, THOUGH THEY SEEM AT FIRST SIGHT TOTALLY UNRELATED WITH EACH OTHER, CAN IN FACT BE SOLVED USING THE SAME TOOLS AND IDEAS FROM GRAPH THEORY. FURTHERMORE, THE DETAILS SOME PROOF WILL BE LEFT TO THE STUDENTS AS A HOMEWORK EXERCISE, ESPECIALLY IN THOSE CASES IN WHICH A CERTAIN PROCEDURE OR IDEA HAS ALREADY BEEN USED IN PREVIOUS PROOFS; IN THIS WAY, STUDENTS WILL BE FORCES TO ABANDON THAT PASSIVE ATTITUDE IN THEIR STUDY HABITS WHICH IS OFTEN A SERIOUS OBSTACLE TO THE IMPROVEMENT OF THEIR LEARNING SKILLS

	Prerequisites
	THE ONLY PRELIMINARY KNOWLEDGES REQUIRED ARE THE BASIC ONES IN LINEAR ALGEBRA AND ABSTRACT ALGEBRA USUALLY GIVEN IN THE STANDARD UNDERGRADUATE COURSES.

	Contents
	[1] HISTORICAL INTRODUCTION TO GRAPH THEORY \|\|\| [2] BASIC NOTIONS: VARIOUS TYPES OF GRAPHS (NON ORIENTED GRAPHS AND DIGRAPHS, MULTIGRAPHS AND SIMPLE GRAPHS, WEIGHTED GRAPHS); MORPHISMS BETWEEN GRAPHS; SUBGRAPHS; OPERATIONS ON GRAPHS. \|\|\| [3] PATHS, WALKS, CYCLES AND ASSOCIATED NOTIONS (METRIC ON A GRAPH, DIAMETER, CIRCUMFERENCE, GIRTH, CENTER, RADIUS). \|\|\| [4] TREES AND FORESTS: VARIOUS CHARACTERIZATIONS OF TREES, SPANNING TREES OF A GRAPH, NORMAL TREES, SEARCH ALGORITHMS IN A GRAPH (DEPTH-FIRST, BREADTH-FIRST). \|\|\| [5] EULERIAN AND HAMILTONIAN GRAPHS: CHARACTERIZATIONS OF EULERIAN CIRCUITS AND ALGORITHM TO CONSTRUCT THEM; HAMILTONIAN CYCLES; SOME HAMILTONICITY CRITERIA (TOUGHNESS, DIRAC THEOREM). \|\|\| [6] MATCHINGS AND COVERINGS: BIPARTITE GRAPHS AND THEIR CHARACTERIZATION VIA THE PARITY OF CYCLES; MATCHINGS AND COVERINGS; MATCHING IN A BIPARTITE GRAPH, HALL THEOREM AND KOENIG THEOREM. \|\|\| [7] CONNECTIVITY: CONNECTED AND K-CONNECTED GRAPHS; VERTEX AND EDGE CONNECTIVITY; WHITNEY INEQUALITIES; MENGER THEOREM; DECOMPOSITION OF A GRAPH IN BLOCKS [8] ALGEBRAIC GRAPH THEORY: VECTOR SPACES ASSOCIATED WITH A GRAPH, ADJACENCY AND INCIDENCE OPERATORS, SPECTRUM OF A GRAPH AND ITS APPLICATIONS (RELATION BETWEEN NUMBER OF EIGENVALUES AND DIAMETER, BOUND ON EIGENVALUES OF A LINE GRAPH, RANKING ALGORITMS FOR WEB SEARCH ENGINES, PAGERANK; SPECTRUM OF A SUBGRAPH), LAPLACIAN AND COBOUNDARY OPERATORS; CUT SPACE AND CYCLE SPACE; COMPLEMENTS OF LINEAR ALGEBRA (ADJOINT OF A LINEAR OPERATOR BETWEEN TWO EUCLIDEAN SPACES; CLASSICAL ADJOINT OF A MATRIX; CAUCHY-BINET FORMULA); MATRIX-TREE THEOREM AND CAYLEY FORMULA; VARIOUS FORMULAS FOR COMPUTING THE NUMBER OF WALKS, PATHS AND CYCLES OF ASSIGNED LENGHT IN A GRAPH; APPLICATIONS OF GRAPH THEORY TO ELECTRICAL NETWORKS ANALYSIS. \|\|\| [9] PLANAR GRAPHS: EULER FORMULA AND ITS FIRST CONSEQUENCES, REGULAR POLYHEDRA, KURATOWSKI'S THEOREM; DUAL OF A GRAPH, WHITNEY PLANARITY CRITERION; EMBEDDING OF A GRAPH INTO A SURFACE, HEAWOOD THEOREM. \|\|\| [10] COLORINGS: VERTEX AND EDGE COLORINGS; K-COLORABILITY; CHROMATIC NUMBER; COLORINGS OF PLANE GRAPHS, 5 COLOR THEOREM AND 4 COLOR THEOREM (WITH THE "PROOF" BY KEMPE); ESTIMATE OF THE CHROMATIC NUMBER VIA THE GREEDY ALGORITHM AND BROOKS THEOREM; NUMBER OF K-COLORINGS, CHROMATIC POLYNOMIAL. \|\|\| [11] NETWORKS AND FLOWS: "MAX-FLOW MIN-CUT" THEOREM AND HOW TO DEDUCE FROM IT THE THEOREMS OF MENGER AND HALL (SEE POINTS [6],[7])

Contents

[1] HISTORICAL INTRODUCTION TO GRAPH THEORY |||

[2] BASIC NOTIONS: VARIOUS TYPES OF GRAPHS (NON ORIENTED GRAPHS AND DIGRAPHS, MULTIGRAPHS AND SIMPLE GRAPHS, WEIGHTED GRAPHS);

MORPHISMS BETWEEN GRAPHS; SUBGRAPHS; OPERATIONS ON GRAPHS. |||

[3] PATHS, WALKS, CYCLES AND ASSOCIATED NOTIONS (METRIC ON A GRAPH, DIAMETER, CIRCUMFERENCE, GIRTH, CENTER, RADIUS). |||

[4] TREES AND FORESTS: VARIOUS CHARACTERIZATIONS OF TREES, SPANNING TREES OF A GRAPH, NORMAL TREES, SEARCH ALGORITHMS IN A GRAPH

(DEPTH-FIRST, BREADTH-FIRST). |||

[5] EULERIAN AND HAMILTONIAN GRAPHS: CHARACTERIZATIONS OF EULERIAN CIRCUITS AND ALGORITHM TO CONSTRUCT THEM; HAMILTONIAN CYCLES;

SOME HAMILTONICITY CRITERIA (TOUGHNESS, DIRAC THEOREM). |||

[6] MATCHINGS AND COVERINGS: BIPARTITE GRAPHS AND THEIR CHARACTERIZATION VIA THE PARITY OF CYCLES; MATCHINGS AND COVERINGS;

MATCHING IN A BIPARTITE GRAPH, HALL THEOREM AND KOENIG THEOREM. |||

[7] CONNECTIVITY: CONNECTED AND K-CONNECTED GRAPHS; VERTEX AND EDGE CONNECTIVITY; WHITNEY INEQUALITIES; MENGER THEOREM;

DECOMPOSITION OF A GRAPH IN BLOCKS

[8] ALGEBRAIC GRAPH THEORY: VECTOR SPACES ASSOCIATED WITH A GRAPH, ADJACENCY AND INCIDENCE OPERATORS, SPECTRUM OF A GRAPH AND ITS

APPLICATIONS (RELATION BETWEEN NUMBER OF EIGENVALUES AND DIAMETER, BOUND ON EIGENVALUES OF A LINE GRAPH, RANKING ALGORITMS FOR WEB

SEARCH ENGINES, PAGERANK; SPECTRUM OF A SUBGRAPH), LAPLACIAN AND COBOUNDARY OPERATORS; CUT SPACE AND CYCLE SPACE; COMPLEMENTS OF

LINEAR ALGEBRA (ADJOINT OF A LINEAR OPERATOR BETWEEN TWO EUCLIDEAN SPACES; CLASSICAL ADJOINT OF A MATRIX; CAUCHY-BINET FORMULA);

MATRIX-TREE THEOREM AND CAYLEY FORMULA; VARIOUS FORMULAS FOR COMPUTING THE NUMBER OF WALKS, PATHS AND CYCLES OF ASSIGNED LENGHT IN

A GRAPH; APPLICATIONS OF GRAPH THEORY TO ELECTRICAL NETWORKS ANALYSIS. |||

[9] PLANAR GRAPHS: EULER FORMULA AND ITS FIRST CONSEQUENCES, REGULAR POLYHEDRA, KURATOWSKI'S THEOREM; DUAL OF A GRAPH, WHITNEY

PLANARITY CRITERION; EMBEDDING OF A GRAPH INTO A SURFACE, HEAWOOD THEOREM. |||

[10] COLORINGS: VERTEX AND EDGE COLORINGS; K-COLORABILITY; CHROMATIC NUMBER; COLORINGS OF PLANE GRAPHS, 5 COLOR THEOREM AND 4

COLOR THEOREM (WITH THE "PROOF" BY KEMPE); ESTIMATE OF THE CHROMATIC NUMBER VIA THE GREEDY ALGORITHM AND BROOKS THEOREM; NUMBER OF

K-COLORINGS, CHROMATIC POLYNOMIAL. |||

[11] NETWORKS AND FLOWS: "MAX-FLOW MIN-CUT" THEOREM AND HOW TO DEDUCE FROM IT THE THEOREMS OF MENGER AND HALL (SEE POINTS [6],[7])

	Teaching Methods
	FRONTAL LECTURES

	Verification of learning
	THE FINAL TEST CONSISTS IN: 1) AN ORAL TEST ON THE CONTENTS OF THE COURSE, WITH THE AIM OF CHECKING THE LEVEL OF UNDERSTANDING OF THE THEORETICAL PART OF THE COURSE; 2) GIVING THE CANDIDATE SOME SIMPLE EXERCISE TO SOLVE, IN ORDER TO TEST HIS/HER ABILITY TO PRACTICALLY APPLY THE THEORETICAL NOTIONS AND THE COMPUTATIONAL TOOLS. FURTHER MOURE, DURING THE WHOLE COURSE THE STUDENTS WILL BE ASSIGNED AUTO-TESTING EXERCICES AS HOMEWORK, AND THEY WILL ALSO BE INVITED TO SOLVE, WITH THE HELP OF THE TEACHER, SOME SIMPLE PROBLEMS IN CLASS.

Verification of learning

THE FINAL TEST CONSISTS IN: 1) AN ORAL TEST ON THE CONTENTS OF THE COURSE, WITH THE AIM OF CHECKING THE LEVEL OF UNDERSTANDING OF THE THEORETICAL PART OF THE COURSE; 2) GIVING THE CANDIDATE SOME SIMPLE EXERCISE TO SOLVE, IN ORDER TO TEST HIS/HER ABILITY TO PRACTICALLY APPLY THE THEORETICAL NOTIONS AND THE COMPUTATIONAL TOOLS. FURTHER MOURE, DURING THE WHOLE COURSE THE STUDENTS WILL BE ASSIGNED AUTO-TESTING EXERCICES AS HOMEWORK, AND THEY WILL ALSO BE INVITED TO SOLVE, WITH THE HELP OF THE TEACHER, SOME SIMPLE PROBLEMS IN CLASS.

	Texts
	R. DIESTEL: GRAPH THEORY (GTM SPRINGER, 2006) B. BOLLOBAS: MODERN GRAPH THEORY (GTM 184, SPRINGER, 1998) N. BIGGS: ALGEBRAIC GRAPH THEORY (CAMBRIDGE UNIVERSITY PRESS, 1993) C. GODSIL, G.F. ROYLE: ALGEBRAIC GRAPH THEORY (GTM 207, SPRINGER, 2001)

BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2016-09-30]