20.500.12556/DKUM-14194 PRESEK TREH NAJDALJŠIH POTI V GRAFU INTERSECTION OF THREE DETOUR PATHS IN GRAPH 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. The problem wheteher the intersection of longest paths in a graph is always nonempty is studied. A special emphasis is given on the intersection of three longest ways, this is treated in Section 4. The first part contains basic definitions from the area of graph theory that are needed later. In the next chapter it is first proved that the intersection of two longest paths is always nonempty, and then the problem is generalized to the intersection of more longest paths. Examples of graphs with empty intersection of the set of all longest path are given. On the other hand, the nonemptiness of the intersection is proved for traceable, hypotraceable, and split graphs. In Chapter 3 the focus is on the intersection of longest paths in graphs that contain cut vertices. It is proved that the intersection is nonempty exactly when the intersection is nonempty in all blocks of the graph. The final chapter is devoted to intersections of three longest paths. The main results asserts that three longest paths always intersect provided that they induce an outer planar graphs. Pot najdaljša pot presek najdaljših poti blok zunanje ravninski graf Hamiltonovo povezan blok skoraj Hamiltonovo povezan dvodelni blok. Path longest path intersection of longest paths block outerplanar graphs Hamilton-connected block almost-Hamilton-connected bipartite block. true true false [N. Valek] Slovenski jezik Angleški jezik Diplomsko delo 2010-05-31 22:13:44 2010-07-07 12:03:37 2022-04-12 11:49:05 2023-12-17 03:28:44 2010 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 17740296 URN:SI:UM:DK:SMMIAN1F UNI_Valek_Natalija_2010.pdf UNI_Valek_Natalija_2010.pdf 1 43876D87DECE588450CCD70E42415AFA edbd1c380882290fe23107a9d1bbd57ce605a057106ea11e1f50b4418a7f1b68 187eb456-7c04-11eb-bb7a-00155d0001ca 20.500.12556/dkum/fa506928-c1b6-4008-a7ea-6a776e567a78 https://dk.um.si/Dokument.php?lang=slv&id=14972 Fakulteta za naravoslovje in matematiko 0 0 0