Corso GE460 - Teoria dei Grafi/ Graph Theory

a.a. 2020/2021

Docente: Margarida Melo

Ufficio 108, Tel: 06 5733 8227, Email: melo---mat.uniroma3.it

Ricevimento:
Dopo le lezioni o per appuntamento.

Programma:

  • Definizioni basiche e esempi.
  • Connetività in grafi. Grafi Euleriani e Hamiltoniani,
  • Alberi. Spazi di cicli e tagli.
  • Planarità.
  • Grafi bipartiti. Matchings. Coloramenti. Flussi.
  • Elementi di teoria Algebrica dei grafi.
  • Introduzione alla teoria dei matroidi.


    • Prerequisiti: Corsi basici di Algebra e Geometria (AL110, GE110).

    Valutazione:

    1) Fogli di esercizi (4) da consegnare e discutere.
    2) Seminario su un tema a scelta. Sarà utile consegnare una piccola tesina con lo svolgimento dei contenuti di ciascun seminario.
    3) Compito scritto sugli argomenti del corso.

    La valutazione finale sara' il massimo tra (1) e (2), (1) e (3) oppure solo (3).

    Diario delle lezioni

    Esercitazione 1
     Esercitazione 2
     Esercitazione 3
    Esercitazione 4
    Esercitazione 5

    Esercizi 1
    Esercizi 2
    Esercizi 3
    Esercizi 4(da consegnare entro 9/06/2021)

    Suggerimenti per argomenti da presentare al seminario

    Seminari presentati da studenti:

    - Applicazioni semplici di T dei grafi (con scoppi didattici): Lemma di Sperner, Teorema dei 5 colori, Problema del commesso viaggiatore
     (a cura di Barbara Galati)
    -     Teorema di Cayley
    (a cura di Antonello D'Angelli)
    - Alberi minimali in grafi pesati e algoritmi di ricerca.
     (a cura di Helena Rivera Dallorto)
    - Teoremi di Ramsey con un'approccio della logica (teorema della compatezza),
    (a cura di Raffaele di Donna)
    - Il teorema di Max-Flow Min-Cut e applicazioni,
    (a cura di Melissa Sordi)
    - Il teorema di Menger (nelle sue varie versioni),
    (a cura di Francesca Percario)
    - Algoritmi di visita in grafi,
     (a cura di Chiara Stortini)
    - Complessità degli algoritmi,
    (a cura di Martina Gusai)
    - Grafi in superficie topologiche,
    (a cura di Giusi Capobianco)
    - Teoria di Ramsey,
    (a cura di Maria Concetta Campailla)
    - Grafi due isomorfi e il teorema di Whitney,
    (a cura di Michele Matteucci)
    - Catene di Markov: parte I,
    (a cura di Sara Giuli)
    -  Catene di Markov: parte II,
    (a cura di Francesca Giulianelli)
    - Matroidi rappresentabili, regolari e loro duali
    (a cura di Lorenzo Bottiglione)
    - Colorazioni di vertici
    (a cura di Rimon Ghobryal)
    - Il teorema di Kirchoff
    (a cura di Martina Miseri)
    - Grafi Hamiltoniani e applicazioni
    (a cura di Sara Magini)
    - Metodi di Teoria dei Grafi per la Teoria dei Codici
    (a cura di Andrea Pelosi)
    - Applicazioni alla crittografia: costruzioni di Hash tramite Expander graphs
    (a cura di Lorenzo Pichetti)
    - PageRank di Google
     (a cura di Riccardo Papa)
    - Applicazione delle Probabilità alla teoria dei grafi
    (a cura di Gabriele Ricci)
    - Introduzioni alla teoria dei nodi
    ( a cura di Chiara Severini)
    - Caratterizzazione di matroidi rappresentabili
     (a cura di Chiara Consorti e Nicole Serena Cianfarani)





    Bibliografia: