Computer Science - Informatica

PAUL JOSEPH WOLLAN
PAUL JOSEPH WOLLAN

Obiettivi generali: Lo studente raggiungerà una piena padronanza dei risultati classici della teoria dei grafi e verrà inoltre a conscenza dei risultati e dei concetti più recenti della ricerca attuale in teroia dei grafi.
Obiettivi specifici: Gli argomenti fondamentali che lo studente conoscerà dopo il corso includono: alberi e alberi spanning in grafi; connettività nei grafi; Cicli Hamiltonian e condizioni sufficienti per la loro esistenza. Teorema di Menger e flussi nei grafici. La teoria dei matching nei grafi inclusi i teoremi di Konig, Hall e Tutte. Teoria dei grafi estremi e la teorema di Turan e la teoria di Ramsey. Grafi planari e la colorazione di grafi.
Conoscenza e comprensione: Lo studente acquisirà padronanza delle tecniche di base utili per le dimostrazioni matematiche e prenderà familiarità con le tecniche più avanzate. Inoltre potrà comprendere sia i risultati fondamentali della teoria dei grafi che le dimostrazioni degli stessi.
Applicazione di conoscenza e comprensione Lo studente prenderà confidenza con il concetto matematico di induzione applicato a diversi contesti e sarà in grado di risolvere in maniera autonoma i problemi di base della teoria dei grafi.
Autonomia di giudizio: Lo studente sarà in grado di selezionare in maniera autonoma gli strumenti matematici necessari per la risoluzione di un problema. Potrà inoltre stabilire quali sono gli argomenti di ricerca più significativi nell'ambito della teoria dei grafi.
Abilità comunicative: Lo studente acquisirà l'abilità di scrivere in maniera rigorosa le dimostrazioni matematiche della disciplina.
Capacità di apprendimento: Al completamento del corso di studi, lo studente sarà in possesso degli strumenti necessari per leggere e comprendere la letteratura scientifica sulla teoria dei grafi e per produrre ricerca originale nel campo.

Conoscenza di base di matematica discreta e le dimostrazione matematiche.

Il corso include: albori e albori di copertura in grafi; la connettività in grafi; cicli Hamiltonian e condizioni per loro esistenze. La teorema di Menger e flussi in grafi. Abbinamento in grafi, incluso i teoremi di Konig, Hall, e Tutte. La teoria estremale di grafi con la teorema di Turan e la teoria di Ramsey. Grafi planari e la colorazione dei grafi.

Graph Theory, 3rd edition, Diestel

Frequenza non obbligatoria

Prova scritta