First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Engineering
ICT FOR INTERNET AND MULTIMEDIA
Course unit
GRAPH THEORY
INP9087848, A.A. 2019/20

Information concerning the students who enrolled in A.Y. 2019/20

Information on the course unit
Degree course Second cycle degree in
ICT FOR INTERNET AND MULTIMEDIA (Ord. 2019)
IN2371, Degree course structure A.Y. 2019/20, A.Y. 2019/20
N0
bring this page
with you
Degree course track INTERNATIONAL MOBILITY [005PD]
Number of ECTS credits allocated 6.0
Type of assessment Mark
Course unit English denomination GRAPH THEORY
Department of reference Department of Information Engineering
Mandatory attendance No
Language of instruction English
Branch PADOVA
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Lecturers
Teacher in charge MICHELANGELO CONFORTI MAT/09

Mutuating
Course unit code Course unit name Teacher in charge Degree course code
SC04105572 DISCRETE MATHEMATICS MICHELANGELO CONFORTI SC1159

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Educational activities in elective or integrative disciplines MAT/09 Operational Research 6.0

Course unit organization
Period Second semester
Year 1st Year
Teaching method frontal

Type of hours Credits Teaching
hours
Hours of
Individual study
Shifts
Practice 3.0 24 51.0 No turn
Lecture 3.0 24 51.0 No turn

Calendar
Start of activities 02/03/2020
End of activities 12/06/2020
Show course schedule 2019/20 Reg.2019 course timetable

Syllabus
Prerequisites: basic knowledge of mathematics (including proof techniques, basic combinatorics etc.)
Target skills and knowledge: Knowledge of the basic results in graph theory; Understanding and applying proof methodologies andtechniques that are common in discrete mathematics.
Examination methods: Written exam.
Assessment criteria: Knowledge of the material presented in class. Authonomous application of proof techniques.
Course unit contents: Undirected graphs: Basic Definitions: walks, paths, cuts, connectivity. Classes of graphs: Bipartite, complete, k-regular, hypercubes.

Trees: Definitions, basic properties, fundamental cycles, minimum spanning tree: Kruskal's algorithm.

Bipartite Matchings: Definitions, alternating-augmenting paths. Hall's theorem, Konig's theorem, stable matchings.

General Matchings: Tutte's theorem, Berge's formula, Gallai's identities.

Directed Graphs: Basic definitions and properties. Strong connectivity, strongly connected components, acyclic digraphs, Tournaments, Hamiltonian paths and cycles in tournaments, Gallai-Milgram theorem, comparability graphs.

Connectivity: Edge and vertex connectivity, 3 Menger theorems, ear decompositions.

Graph Coloring: Edge-Chromatic number, Vizing's theorem, Chromatic number.

Planarity. Plane drawings and dual graphs, Euler's formula, colorability of planar graphs, Kuratowski theorem , Tait's theorem.

Traversability. Hamiltonian and Eulerian Graphs.
Planned learning activities and teaching methods: 24 lectures of 2 hours each.
Additional notes about suggested reading: Detailed information can be found in
https://sites.google.com/view/micheleconforti/teaching
Textbooks (and optional supplementary readings)
  • Bondy, John Adrian; Murty, U. S. R., Graph theory. New York: Springer, --. Cerca nel catalogo
  • Bollobas, Bela, Modern graph theory. New York: Springer, --. Cerca nel catalogo