Povezanost v produktih grafov

magistrsko delo

Sandra Cigula (Avtor), Simon Špacapan (Mentor)

Povzetek

V tej nalogi bomo obravnavali pojma povezanost po povezavah in povezanost po vozliščih v produktih grafov. Drugi cilj bo opisati strukturo in ostale lastnosti najmanjših presečnih množic vozlišč in najmanjših presečnih množic povezav v produktih grafov. Osredotočili se bomo predvsem na kartezični, direktni, krepki in leksikografski produkt grafov. Zanimalo nas bo, kako izraziti povezanost produkta z lastnostmi posameznih faktorjev produkta, kot so najmanjša stopnja, red grafa in povezanost. Pri direktnem produktu grafov bomo ugotovili, da je povezanost po povezavah odvisna od povezanosti faktorjev, pa tudi od tega, kako daleč sta faktorja $G$ in $H$ od tega, da bi bila dvodelna. Nato bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav kartezičnih produktov grafov. Podan bo dokaz trditve $lambda(G , Box , H)= textrm{min}left{lambda(G)left|V(H)right|,lambda(H)left|V(G)right|,delta(G)+delta(H)right}.$ Dokaz podobne trditve za povezanost po vozliščih kartezičnega produkta bo naveden v nadaljevanju. Na koncu bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav krepkih produktov grafov in povezanost v leksikografskem produktu.

Ključne besede

magistrska dela;produkti grafov;kartezični produkt;direktni produkt;krepki produkt;leksikografski produkt;povezanost;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2016
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[S. Cigula]
UDK:	519.171(043.2)
COBISS:	22455560
Št. ogledov:	1024
Št. prenosov:	135
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Connectivity of graph products
Sekundarni povzetek:	In this thesis we discuss edge and vertex connectivities of graph products. The aim is to determine the connectivity of all four standard graph products and describe the structure of minimum edge-cut sets. We will study how to express the connectivity of the product with properties of its factors, such as minimum degree, order and connectivity. For the edge connectivity of direct product of graphs we find that connectivity of the product depends not only on connectivities of its factors but also on how far the factors $G$ and $H$ are from being bipartite. Then we discuss the structure and other properties of minimum edge-cuts in Cartesian product of graphs. We present the proof of the following result $lambda(G , Box , H)= textrm{min}left{lambda(G)left\|V(H)right\|,lambda(H)left\|V(G)right\|,delta(G)+delta(H)right}.$ Proof of a similar claim for vertex connectivity of Cartesian products of graphs will also be presented. Finally we consider the size and the structure of minimum edge-cuts in strong products of graphs and edge and vertex connectivities of lexicographic product.
Sekundarne ključne besede:	graph products;Cartesian product;direct product;strong product;lexicographic product;connectivity;master theses;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Magistrsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	XI, 68 str.
ID:	9137753