First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Science
MATHEMATICS
Course unit
DISCRETE MATHEMATICS
SC04105572, A.A. 2018/19

Information concerning the students who enrolled in A.Y. 2016/17

Information on the course unit
Degree course First cycle degree in
MATHEMATICS
SC1159, Degree course structure A.Y. 2008/09, A.Y. 2018/19
N0
bring this page
with you
Number of ECTS credits allocated 6.0
Type of assessment Mark
Course unit English denomination DISCRETE MATHEMATICS
Website of the academic structure http://matematica.scienze.unipd.it/2018/laurea
Department of reference Department of Mathematics
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

Mutuated
Course unit code Course unit name Teacher in charge Degree course code
INP7080667 GRAPH THEORY MICHELANGELO CONFORTI IN2371
INP7080667 GRAPH THEORY MICHELANGELO CONFORTI IN2371

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Core courses MAT/09 Operational Research 6.0

Course unit organization
Period Second semester
Year 3rd 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 25/02/2019
End of activities 14/06/2019

Examination board
Board From To Members of the board
7 Matematica Discreta - a.a. 2018/2019 01/10/2018 30/09/2019 CONFORTI MICHELANGELO (Presidente)
DI SUMMA MARCO (Membro Effettivo)
DE FRANCESCO CARLA (Supplente)
DE GIOVANNI LUIGI (Supplente)
RINALDI FRANCESCO (Supplente)

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

Innovative teaching methods: Teaching and learning strategies
  • Problem based learning
  • Case study
  • Problem solving

Innovative teaching methods: Software or applications used
  • Mathematica

Sustainable Development Goals (SDGs)
Quality Education