Follow us
Search

GRAPH THEORY

Academic Year 2017/2018 - 3° Year - Curriculum GENERALE
Teaching Staff: Lorenzo Maria Filippo Milazzo
Credit Value: 6
Scientific field: MAT/03 - Geometry
Taught classes: 48 hours
Term / Semester:

Learning Objectives

The couse has the following objectives:

Knowledge and understanding:

- Mathematic Instruments in graph theory such as theorems and algoritms will be provide in the course. They permit to develop mathematical abilities in reasoning and calculation. These abilities could permit to resolve known problems by mathematical model.

Applying and knowledge and understanding:

- At the end of course student will be able to get knowledge for a tightened use of new mathematical techniques and an understanding of treated arguments in such way to link them each other.

Making judgements:

- Course is based on logical-deductive method which wants to give to students authonomus judgement useful to understanding incorrect method of demonstration also, by logical reasoning, student will be able to face not difficult problems in graph theory with teacher's help.

Communication skills:

- In the final exam, student must show for learned different mathematical techniques an adapt maturity on oral communication using also multimedia tools.

Learning skills

- Autonomously student will be able to face application and theoretical arguments which could be studied in new classes or in different working fields; for example flow theory and connectivity have huge application on telecommunications field (Local Area Network and Metropolitan Area Network: LAN e MAN), on electrical and communication fields (Industrial design).


Detailed Course Content

Basic definition on Graph Theory. Cycles and cocycles. Cyclomatic and cocyclomatic numbers. Planar graph and their property. Euler's formula. Tree and cotree. Spanning tree. Strongly and minimally connected graphs and their property. The shortest path and maze’s problem. Center and radii. Maximum flow and maximum compatible flow. Ford and Fulkerson theorem. Maximum and perfect matchings. Covering and minimum covering of a graph. Matching in bipartite graph, Köenig's theorem. Hamiltonian and Eulerian graphs. Edge and vertex colourings, chromatic number and index number. Vizing's theorem. Chromatic polynomial. Decomposition of complete graph in Steiner triple systems. Bicolorings of STSs. Upper and lower chromatic numbers.


Textbook Information

  1. C. Berge, "Graph and Hypergraph", Elsevier.
  2. D. West, "Introduction to Graph Theory", Illinois University.