Fabrizio PUGLIESE | GRAPH THEORY
Fabrizio PUGLIESE GRAPH THEORY
cod. 0512300028
GRAPH THEORY
| 0512300028 | |
| DIPARTIMENTO DI MATEMATICA | |
| EQF6 | |
| MATHEMATICS | |
| 2022/2023 |
| YEAR OF COURSE 3 | |
| YEAR OF DIDACTIC SYSTEM 2018 | |
| AUTUMN SEMESTER |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| MAT/03 | 6 | 48 | LESSONS |
| Objectives | |
|---|---|
| THE MAIN AIM OF THE COURSE IS TEACHING THE FUNDAMENTAL NOTIONS OF GRAPH THEORY, AND TO SHOW SOME OF ITS MOST IMPORTANT APPLICATIONS. - KNOWLEDGE AND UNDERSTANDING: THE STUDENT WILL BE ACQUAINTED WITH THE BASICS OF GRAPH THEORY AND ITS APPLICATIONS. IN PARTICULAR, HE/SHE WILL SEE HOW, STARTING FROM SUCH AN ELEMENTARY STRUCTURE SUCH AS THAT OF A GRAPH, ONE CAN BUILD A THEORY EXTREMELY RICH FROM VARIOUS VIEWPOINTS: TOPOLOGICAL (IMMERSIONS OF GRAPHS INTO SURFACES, COLORABILITY, ETC.), ALGEBRAIC (SPECTRAL GRAPH THEORY, POLYNOMIAL INVARIANTS, MORPHISMS) AND COMBINATORIAL. FURTHERMORE, THE STUDENT WILL BE ACQUAINTED WITH SOME FUNDAMENTAL APPLICATIONS, IN PARTICULAR TO OPTIMIZATION PROBLEMS (DIJKSTRA ALGORITHM, KRUSKAL ALGORITHM, FORD-FULKERSON ALGORITHM, MATCHING PROBLEMS, ETC.) - APPLYING KNOWLEDGE AND UNDERSTANDING: THE AIM IS TO ENABLE STUDENTS TO APPLY THE THEORETICAL NOTIONS AND COMPUTATIONAL TOOLS THEY WILL LEARN. TO THIS AIM, MANY LECTURES WILL BE DEVOTED TO PROBLEM SESSIONS (ABOUT 1/3 OF THE TOTAL AMOUNT OF TIME); BESIDES THE PROBLEMS DISCUSSED IN THE CLASSROOM, A FEW MORE WILL BE ASSIGNED AS HOMEWORK. |
| 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; 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. |
| 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/LECTNOTES.HTM) - 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) |
| More Information | |
|---|---|
| EMAIL: fpuglies@unisa.it |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2024-08-21]
