Računanje notranjega obsega ravninskih grafov

delo diplomskega seminarja

Klementina Pirc (Avtor), Sergio Cabello (Mentor)

Povzetek

Seznanili se bomo s pojmom notranjega obsega ravninskega grafa in predstavili algoritem za njegov izračun s časovno zahtevnostjo O(nlog n) ter del algoritma z linearno zahtevnostjo. Podrobneje si bomo ogledali še povezavo med notranjim obsegom in najmanjšim prerezom ravninskih grafov.

Ključne besede

teorija grafov;notranji obseg;ravninski grafi;algoritmi;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2021
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[K. Pirc]
UDK:	519.17
COBISS:	58400259
Št. ogledov:	822
Št. prenosov:	80
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Computing the girth of a planar graph
Sekundarni povzetek:	After acquainting ourselves with the girth of a planar graph, we first examine an algorithm for computing it in time O(nlog n). Second, we take a look at another procedure that runs in linear time and finally, we examine the connection between the girth and the minimum cut in planar graphs.
Sekundarne ključne besede:	graph theory;girth;planar graphs;algorithms;
Vrsta dela (COBISS):	Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program:	0
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Strani:	29 str.
ID:	12512664