Fabrizio PUGLIESE | GRAPH THEORY
Fabrizio PUGLIESE GRAPH THEORY
cod. 0512300028
GRAPH THEORY
| 0512300028 | |
| DEPARTMENT OF MATHEMATICS | |
| EQF6 | |
| MATHEMATICS | |
| 2024/2025 |
| YEAR OF COURSE 3 | |
| YEAR OF DIDACTIC SYSTEM 2018 | |
| SPRING SEMESTER |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| MAT/03 | 6 | 48 | LESSONS |
| Exam | Date | Session | |
|---|---|---|---|
| TEORIA DEI GRAFI | 07/01/2025 - 09:00 | SESSIONE DI RECUPERO | |
| TEORIA DEI GRAFI | 27/01/2025 - 09:00 | SESSIONE DI RECUPERO | |
| TEORIA DEI GRAFI | 17/02/2025 - 09:00 | SESSIONE DI RECUPERO |
| 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 (BUT NOT MANDATORY) PRELIMINARY KNOWLEDGES ARE THE BASIC ONES IN LINEAR ALGEBRA AND ABSTRACT ALGEBRA USUALLY GIVEN IN THE STANDARD UNDERGRADUATE COURSES. |
| Contents | |
|---|---|
| THE COURSE CONSISTS OF A SINGLE 48 HOURS UNIT. BELOW YOU FIND THE DETAILED PROGRAM. 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; DUAL GRAPH AND WHITNEY'S PLANARITY CRITERION; DEMOUCRON'S PLANARITY TEST. GRAPH GENUS; EMBEDDINGS OF K_5 AND K_3,3 INTO THE TORUS. 7. COLORINGS (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; SPECTRAL PROPERTIES OF GRAPHS; FLOW SPACE AND CUT SPACE; MATRIX-TREE THEOREM. |
| Teaching Methods | |
|---|---|
| THE COURSE IS DIVIDED INTO LECTURES (32 HOURS) AND PROBLEM SESSIONS (16 HOURS). DURING THE LECTURES THE RESULTS OF GRAPH THEORY LISTED IN SECTION "CONTENTS OF THE COURSE" WILL BE EXPOSED; IN THE PROBLEM SESSIONS IT WILL BE TAUGHT HOW TO APPLY SUCH RESULTS TO CONCRETE PROBLEMS; FURTHERMORE, THE PROOF OF SOME SIMPLER THEOREMS WILL BE SPLIT INTO AS A SEQUENCE OF EXERCISES, WHOSE SOLUTION WILL TRAIN THE STUDENT TO REASON AUTONOMOUSLY AND MAKE HIS/HER OWN PROOFS. BESIDES THE PROBLEMS DISCUSSED IN THE CLASSROOM, A FEW MORE WILL BE ASSIGNED AS HOMEWORK, TO ENHANCE THE STUDENT'S CAPACITY TO SOLVE PROBLEMS ON HIS/HER OWN. |
| Verification of learning | |
|---|---|
| THE EXAM IS ORAL AND APPROXIMATELY 45 MINUTES LONG. THE STUDENTS WILL BE ASKED TO ANSWER TWO QUESTIONS ON THE THEORY AND TO DISCUSS THE SOLUTION OF ONE OF THE PROBLEMS PROPOSED IN CLASSROOM OR AS HOMEWORK; THE FINAL EXAMINATION MARK WILL BE A WEIGHTED COMBINATION OF THE THREE ANSWERS, THE WEIGHTS BEING APPROXIMATELY 30% FOR EACH OF THE TWO THEORETICAL QUIZZES AND 40% FOR THE DISCUSSION OF THE EXERCISE. THE RESULT OF THE EXAM WILL BE EXPRESSED BY A SCORE BETWEEN 0/30 AND 30/30. IN ORDER TO PASS THE EXAM WITH A MINIMUM SCORE, THE STUDENT MUST SHOW AT LEAST A BASIC KNOWLEDGE OF THE CONTENTS OF THE COURSE. THE "30/30 CUM LAUDE" WILL BE GIVEN TO CANDIDATES SHOWING A REAL MASTERY OF THE PROGRAM AND THE ABILITY TO APPLY THE ACQUIRED NOTIONS AND COMPUTATIONAL TECHNIQUES EVEN IN SITUATIONS SLIGHTLY DIFFERENT FROM THOSE SEEN DURING THE COURSE. |
| Texts | |
|---|---|
| REFERENCE TEXTS: - F.PUGLIESE: APPUNTI ED ESERCIZI SVOLTI SU ARGOMENTI DI TEORIA DEI GRAFI (REPERIBILI AL LINK HTTPS://DOCENTI.UNISA.IT/004411/RISORSE) - T. HARJU, GRAPH THEORY, LECTURE NOTES (2012, REPERIBILI AL LINK HTTPS://USERS.UTU.FI/HARJU/GRAPHTHEORY/GRAPHTHEORY.PDF) - C. GODSIL, G. ROYLE, ALGEBRAIC GRAPH THEORY (SPRINGER 2001) TEXTS FOR FURTHER READING: - B. BOLLOBAS, MODERN GRAPH THEORY (SPRINGER 1998) - D. WEST, INTRODUCTION TO GRAPH THEORY (PRENTICE HALL 1996) - J.A. BONDY, U.S.R. MURTY, GRAPH THEORY (SPRINGER 2008) - M. AIGNER, DISCRETE MATHEMATICS (AMERICAN MATHEMATICAL SOCIETY 2007) |
| More Information | |
|---|---|
| EMAIL: fpuglies@unisa.it |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2024-11-29]
