Karakterizacija reducibilnih šestkotnikov elementarnih benzenoidnih grafov

diplomsko delo

Milan Černel (Avtor), Andrej Taranenko (Mentor)

Povzetek

Benzenoidni graf je končen, povezan v ravnino vložen graf brez presečnih vozlišč, v katerem je vsako lice omejeno s pravilnim šestkotnikom z dolžino stranice ena. Benzenoidni graf G je elementaren, če vsaka povezava pripada nekemu 1-faktorju grafa G. Šestkotnik h elementarnega benzenoidnega grafa je reducibilen, če tudi po odstranitvi mejnih povezav in vozlišč tega šestkotnika, graf ostane elementaren benzenoidni graf. Karakteriziramo reducibilne šestkotnike elementarnega benzenoidnega grafa. Karakterizacija je osnova za algoritem, s katerim se ugotovi zaporedje reducibilnih šestkotnikov, ki dekompozirajo graf iz te družine, v času O(n2). Ob tem je predstavljen algoritem, ki dekompozira elementarni benzenoidni graf z največ eno perikondenzirano komponento v linearnem času.

Ključne besede

matematika;šestkotniki;grafi;vrh;dolina;lice;benzenoidni grafi;reducibilnost;dekompozicija;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2011
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[M. Černel]
UDK:	51(043.2)
COBISS:	18406408
Št. ogledov:	2207
Št. prenosov:	151
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	CHARACTERIZATION OF REDUCIBLE HEXAGONS OF ELEMENTARY BENZENOID GRAPHS
Sekundarni povzetek:	A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-faktor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagon of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagon that decomposes a graph of this class in O(n2) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.
Sekundarne ključne besede:	graph;peak;valley;face;benzenoid graph;1-factor / perfect matching;reducible hexagon;reducible face decomposition;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	34 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19293