Å fange strukturen på nettverk

Grafar (det dei fleste vil kjenne igjen som "nettverk": prikkar med liner mellom) er mykje brukte i dataverda for å representere alle slags relasjonar: Venskapsband mellom folk, vegar mellom stader, slektskap mellom arter, handel mellom firma og mykje meir. Strukturen på slike relasjonar er ikkje alltid lettfatteleg, korkje for menneske eller datamaskiner, og me treng ulike verkty for å kunne synleggjere slike strukturar.

Eit uunnverleg verkty er i så måte å leggje komponentane i grafen (prikkane og linene) inn i eit tre. Tre har ein enklare struktur, og om grafen kan leggjast inn i eit tre som gjenspeglar strukturen på grafen, så oppnår me ei større forståing av denne strukturen. Kor godt strukturen "passar inn" i treet vert fanga av numeriske mål-funksjonar. Høgemo har i avhandlinga teke føre seg tre forskjellige verkty av denne sorten.

Det største fokuset i avhandlinga er på såkalla spaltetre, som gjev oppskrifter for korleis ein graf kan takast frå einannan, bit for bit. Spaltetre er svært nyttige for ei rekkje viktige problem, og har vorte påkomne av mange forskarar i ulike samanhengar og under ulike namn. Her har forfattaren samla saman trådar frå fleire område av datavitskapen for å gje den fyrste einskapelege framstillinga av spaltetre og dei tilknytte mål-funksjonane deira.

I tillegg har forfattaren sett på ei klasse av grafar (såkalla "lauv-knytingar", eller leaf powers) som kan genererast ut ifrå tre, som gjev ei god tilnærming til korleis slektskap mellom arter gjenspeglar livets tre. Han har synt at enkelte slike grafar berre kan genererast ut ifrå svært store tre, noko som inneber at denne grafklassa kanskje er meir komplisert enn ein tidlegare rekna med.

Personalia

Svein Høgemo (f. 1995) kjem frå Osterøy. Han byrja på doktorgradstudiet ved UiB hausten 2019 under rettleiing av Jan Arne Telle. Han har bachelor i datateknologi frå 2017 og mastergrad i informatikk frå 2019, desse òg tekne ved UiB.