Uporabna diskretna matematika 2015-16

Izvajata: R. Skrekovski in J. Azarija

Glavna tema: Algebrajska teorija grafov

Vsebina

• I. Splosno o grafih: osnove teorije grafov, drevesa, sprehodi, usmerjeni grafi, povezanost, ravninski grafi, barvanja grafov
• II. Program Sage: Uporaba programskega paketa Sage za delo in raziskovanje v teoriji grafov
• III. Spektralna teorija grafov in njena uporaba
• IV. Grafi in grupe: avtomorfizmi, tranzitivni grafi, Cayley-jevi grafi
• A1. Krepko regularni grafi
• A2. Paley-jevi grafi
• A3. Izomorfizem grafov
• A4. Matroidi
• A5. Kleteke
• A6. Nikjer-nicelni pretoki

Izpitni roki

Prosojnice

Splosno o grafih

• Osnovno o grafih
• Drevesa
• Eulerjevi grafi
• Hamiltonovi grafi
• Usmerjeni grafi
• Turnirji
• Povezanost grafov
• Ravninski grafi
• Barvanja grafov

Kromaticni polinom, pretoki

• Barvanja grafov (slajdi 9. in 10.)
• Kromaticni polinom
• Nikjer-nicelni pretoki
• Spekter grafa

Zbornik

• Zbornik (11.8.2016)

Prezentacije studentov

• LaTeX datoteke

Literatura:

• DS 2 - zapiski predavanj
• A. Bondy, U.S.R.. Murty, Graph Theory , Springer, 2008.
• M. Juvan in P. Potocnik: Teorija grafov in kombinatorika: primeri in resene naloge, Drustvo matematikov, fizikov in astronomov Slovenije, 2000.
• Uvod v algebrsko teorijo grafov (Jernej Azarija)
• C.D. Godsil, B.D. McKay - Constructing cospectral graphs
• C.D. Godsil - Are allmost all graphs cospectral?
• N. L. Biggs, Algebraic Graph Theory , Cambridge University Press, 1993.