Izbrana Poglavja iz Diskretne Matematike 2011-12

Vsebina

• I. Splosno o grafih: osnove teorije grafov, povezanost, usmerjeni grafi, ravninski grafi
• II. Velika omrezja: Erdos-Renyi-jev model slucajnih grafov, mali svetovi, brezlestvicna omrezja, geografski modeli, dvovrstna omrezja in drugi modeli. Mere sredisnosti in pomembnosti, ranljivost omrezja, korelacija stopenj tock, koeficient grupiranja in druge mere. Uporaba entropije in spektra. Program Pajek
• III. Barvanja, pokritja in pretoki grafov: Kriticni grafi. Kromaticni polinom. Barvanja ravninskih grafov in grafov vlo\v zenih na ploskvah visjega roda. Seznamska barvanja. Homomorfizmi, frakcijsko in cirkularno barvanje. Barvanja povezav in snarki. Nikjer-nicelni k-pretoki in Tuttove hipoteze o 3-, 4- in 5-pretoku. Cirkularni pretoki in Jaegerjeva hipoteza. Dvojna pokritja in hipoteze o pokritjih in dekompozicijah.
• IV. Spektralna teorija grafov: Problem izomorfizma in izospektralni grafi, nekatere lastnosti grafovskega spektruma, Laplacov spektrum in Kirchoffov izrek o vpetih drevesih.

  Izpitni roki

  • (petek) 22.6. ob 14h
  • (cetrtek) 12.7. ob 12h
  • (cetrtek) 19.7. ob 14h
  • (cetrtek) 2.8. ob 14h
  • (cetrtek) 9.8. ob 14h
  • (petek) 24.8. ob 10h
  • (cetrtek) 30.8. ob 14h
  • (torek) 18.9. ob 14h
  • (ponedeljek) 24.9. ob 14h
  • zadnji - enkrat v oktobru.

  Zbornik in prezentacije studentov - Velika Omrezja

  • LaTeX datoteke za zbornik
  • Zbornik
  • Indeksi centralnosti in algoritmi za njihov izračun (Domen Blenkuš, Matej Filip, Tilen Marc in Aljaž Zalar)
  • Dodelitve vlog (Andreja Zorko, Lucka Lenic, Lea Letnar, Klavdija Jagar)
  • Povezanost (Miha Erzen, Zala Herga, Nika Sustersic, Nina Zupancic)
  • Spekter grafov (Katarina Stupica, Jaka Speh, Teja Segula, Leon Lampret)
  • Napredni koncepti centralnosti (Blazka Hunski, Barbara Ikica, Ana Spela Hodnik)
  • Lokalna gostost (Maruša Povhe, Neva Port, Matej Pirnat, Špela Podgoršek)
  • Primerjava Omrezij (Teja Klemencic, Jerneja Pikelj, Maja Smrke)
  • Omrezne strukture v resnicnem svetu in njihovi mehanicni omrezni modeli (Simon Skerjanec)
  • Grucavost (Uros Kovac, Katarina Zadraznik, Maja Alif)
  • Risanje velikih grafov (Gasper Azman)
  • Mere kompleksnih mrez (Ajda Pirnat, Julia Cafnik, Ziva Mitar)

  Literatura

  Splosno o grafih

  • 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.

  Barvanja grafov

  • Barvanja Grafov - skripta
  • Pretoki in Pokritja - skripta
  • Osnovno o seznamskih barvanjih (Martin Juvan)
  • Zvezdno kromaticno stevilo grafov (Blaz Zmazek)
    (Pozor: zvezno kromaticno stevilo je prastaro ime za kroznega oz. cirkularnega)
  • Kriticni grafi prezentacija , zagovor , diplomski seminar (Andreja Zorko)
  • Brooksov izrek (Riste Skrekovski)
  • Kriticni grafi (Riste Skrekovski)
  • Seznamska barvanja (Riste Skrekovski)
  • Homomorfizmi ravninskih grafov z velikim notranjim obsegom (Matej Mislej)
    (v diplomi najdete osnove homomorfizmov, kroznega barvanja, deljenega barvanja in kroznih pretokov)
  • Razdaljna barvanja grafov (Rok Erman)
  • Injektivna barvanja grafov (Borut Lužar)

  Spektralna teorija grafov

  • 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.