Kromatski polinomi i njihovi korijeni

diplomski rad

• Autor: Josipa Rehlicki
• Mentor: Tomislav Došlić (mentor)
• Član povjerenstva: Tomislav Došlić (predsjednik povjerenstva)
• Član povjerenstva: Boris Guljaš (član povjerenstva)
• Član povjerenstva: Dragutin Svrtan (član povjerenstva)
• Član povjerenstva: Ljiljana Arambašić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2016-09-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom diplomskom radu bavili smo se bojenjem grafova. Krenuli smo od problema koji je desetljećima zadavao teškoće matematičarima, Problem 4-boje. Taj smo si problem matematički predočili kroz grafove. Nakon što smo definirali glavne pojmove vezane za bojenje grafova kao sto su kromatski broj i kromatski polinom, zanimalo nas je postoji li veza između kromatskih korijena i nekih poznatih brojeva. Prvo smo proučavali Fibonaccijeve brojeve i njihovo poopćenje, tj. n-anaccijeve konstante. Nakon što smo došli do važnih zaključaka, prešli smo na metalne sredine. Poveznica tih dvaju skupova brojeva je zlatni rez ili zlatna sredina koja je 2-anaccijeva konstanta, a ujedno i jedna od metalnih sredina. Paralelno prateći dokaz koji vrijedi za 2 n-anaccijeve konstante, dokazali smo da isti rezultat vrijedi i za sve metalne sredine. Zatim smo definirali Berahine brojeve. Tu nismo mogli općenito reći da nešto vrijedi za sve Berahine brojeve, ali najvažnije je da možemo pretpostaviti da se skup kromatskih korijena familije planarnih grafova sastoji od 0,1 i gustog podskupa od (32/27, 4). Zadnje smo jos spomenuli Pisot–Vijayaraghavanove brojeve. Glavno obilježje tih brojeva je da su njihovi konjugati po modulu manji od 1 što znači da oni ne mogu biti kromatski korijeni. Na kraju ovog diplomskog rada, vratili smo se na kromatske intervale. Točnije, bavili smo se samo neseparabilnim grafovima s k-razapinjućim stablima, za k ≤ 3, jer za njih možemo proširiti interval koji ne sadrži kromatske korijene.

Sažetak (engleski)

In this thesis we have studied graph coloring. We started with problem that troubled mathematicians for decades, named 4-color problem. We presented this problem mathematically through graphs. After we defined important terms for graph coloring, like chromatic number and chromatic polynomial, we wondered is there any connection between chromatic roots and some known numbers. First, we analyzed Fibonacci numbers and their generalizations, precisely n-anacci constants. After we came to important conclusions, we considered metallic means. Connection of those two sets of number is the golden ratio or golden mean which is 2-anacci constant, also one of metallic means. Parallel with the following proof that applies to 2n-anacci constants, we have shown that the same result is true for all metallic means. Secondly, we defined Beraha numbers. Here we couldn’t generally say something valid for all Beraha’s numbers, but the most important thing is that we can suppose that chromatic roots for plane graph family contain 0,1 and dense subset of (32/27,4). At the last, we mentioned Pisot–Vijayaraghavan numbers. The main characteristic of these numbers is that their conjugates are less than 1 in absolute value, which means they cannot be chromatic roots. At the end of this thesis, we returned to the chromatic intervals. Precisely, we studied nonseparable graphs with k-spanning trees, for k ≤ 3, because for them we can expand the interval which does not contains chromatic roots.

• Ključne riječi: bojenje grafova; problem 4-boje; Fibonaccijeve brojeve i njihovo poopćenje; Berahini brojevi; Pisot–Vijayaraghavanovi brojevi; neseparabilni grafovi
• Ključne riječi (engleski): graph coloring; 4-color problem; Fibonacci numbers and their generalizations; Beraha numbers; Pisot–Vijayaraghavan numbers; nonseparable graphs
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:783619
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta
• Datum i vrijeme pohrane: 2019-02-05 13:12:01