PRESEK TREH NAJDALJŠIH POTI V GRAFUValek, Natalija (Avtor) Klavžar, Sandi (Mentor) Potnajdaljša potpresek najdaljših potiblokzunanje ravninski grafHamiltonovo povezan blokskoraj Hamiltonovo povezan dvodelni blok.Diplomsko delo obravnava problem preseka najdaljših poti v grafu. Poseben poudarek je na preseku treh najdaljših poti, kateremu je namenjeno četrto poglavje. V prvem delu so zapisane osnovne definicije s področja teorije grafov, ki se uporabljajo v nadaljevanju. V naslednjem poglavju se najprej dokaže nepraznost preseka dveh najdaljših poti, nato pa se presek iz dveh najdaljših poti posploši na presek n najdaljših poti. Podanih je nekaj grafov s praznim presekom najdaljših poti. V zadnjem delu poglavja se dokaže nepraznost preseka za sledljiv, hiposledljiv in razcepljen graf. Sledi poglavje, v katerem se osredotočimo na presek najdaljših poti v posameznih blokih grafa. Dokaže se, da je presek najdaljših poti v grafu neprazen natanko tedaj, ko je neprazen presek v vseh blokih grafa. Zadnje poglavje je namenjeno preseku treh najdaljših poti. Podan je tudi dokaz o nepraznosti preseka treh najdaljših poti v zunanje ravninskih grafih.[N. Valek]20102010-05-31 22:13:44Diplomsko delo14194UDK: 51(043.2)COBISS_ID: 17740296NUK URN: URN:SI:UM:DK:SMMIAN1Fsl