Žerovnik, Janez; matematični kolokvij november 2003

Iz MaFiRaWiki

Grafi v komunikacijah

Janez Žerovnik

Univerza v Mariboru

13. november 2003


Teorija grafov je v zadnjih desetletjih med najbolj živahnimi področji matematike. Nedvomno gre to v veliki meri na račun široke uporabnosti. Tu si bomo ogledali dva primera uporabe teorije grafov. Prvi primer je povezan z modeliranjem usmerjanja sporočil v komunikacijskih ali računalniških mrežah, drugi pa z dodeljevanjem kanalov v sistemih mobilne telefonije. Usmerjanje v grafu je množica poti med vsemi pari vozlišč. Usmerjanje je optimalno, če so vse poti najkrajše. Že dolgo je znano, da v Cayleyevih grafih vedno obstaja optimalno usmerjanje, nekaj časa pa je bila odprta domneva, da trditev velja tudi za po vozliščih tranzitivne grafe. Videli bomo, da je protiprimer za to domnevo kar graf dodekaedra. Za protiutež bomo omenili pozitiven rezultat, ki govori o preprosti in učinkoviti rešitvi za permutacijsko usmerjanje na krožnih grafih. Dodeljevanje kanalov v sistemih mobilne telefonije običajno modeliramo z nalogami, ki so posplošitve barvanja grafov.

Osebna orodja