PRESEK TREH NAJDALJŠIH POTI V GRAFU

Valek, Natalija

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	PRESEK TREH NAJDALJŠIH POTI V GRAFU
Authors:	ID Valek, Natalija (Author) ID Klavžar, Sandi (Mentor) More about this mentor...
Files:	UNI_Valek_Natalija_2010.pdf (1,62 MB) MD5: 43876D87DECE588450CCD70E42415AFA PID: 20.500.12556/dkum/fa506928-c1b6-4008-a7ea-6a776e567a78
Language:	Slovenian
Work type:	Undergraduate thesis
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	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.
Keywords:	Pot, najdaljša pot, presek najdaljših poti, blok, zunanje ravninski graf, Hamiltonovo povezan blok, skoraj Hamiltonovo povezan dvodelni blok.
Place of publishing:	Maribor
Publisher:	[N. Valek]
Year of publishing:	2010
PID:	20.500.12556/DKUM-14194
UDC:	51(043.2)
COBISS.SI-ID:	17740296
NUK URN:	URN:SI:UM:DK:SMMIAN1F
Publication date in DKUM:	07.07.2010
Views:	2957
Downloads:	228
Metadata:
Categories:	FNM
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:	English
Title:	INTERSECTION OF THREE DETOUR PATHS IN GRAPH
Abstract:	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.
Keywords:	Path, longest path, intersection of longest paths, block, outerplanar graphs, Hamilton-connected block, almost-Hamilton-connected bipartite block.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back