Karakterizacija reducibilnih šestkotnikov elementarnih benzenoidnih grafov

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2011
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[M. Černel]
UDC:	51(043.2)
COBISS:	18406408
Views:	2207
Downloads:	151
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	CHARACTERIZATION OF REDUCIBLE HEXAGONS OF ELEMENTARY BENZENOID GRAPHS
Secondary abstract:	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.
Secondary keywords:	graph;peak;valley;face;benzenoid graph;1-factor / perfect matching;reducible hexagon;reducible face decomposition;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	34 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19293