prikaz prve stranice dokumenta Spektar grafa
  Preuzmi
PDF 426.76 KB
diplomski rad
Spektar grafa
2018. urn:nbn:hr:126:517123
Petovari, Iva
Sveučilište Josipa Jurja Strossmayera u Osijeku
Odjel za matematiku
Zavod za primijenjenu matematiku i računarstvo
Katedra za računarstvo i strojno učenje

Citirajte ovaj rad

Petovari, I. (2018). Spektar grafa (Diplomski rad). Osijek: Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:126:517123

Petovari, Iva. "Spektar grafa." Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, 2018. https://urn.nsk.hr/urn:nbn:hr:126:517123

Petovari, Iva. "Spektar grafa." Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, 2018. https://urn.nsk.hr/urn:nbn:hr:126:517123

Petovari, I. (2018). 'Spektar grafa', Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, citirano: 09.11.2024., https://urn.nsk.hr/urn:nbn:hr:126:517123

Petovari I. Spektar grafa [Diplomski rad]. Osijek: Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku; 2018 [pristupljeno 09.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:126:517123

I. Petovari, "Spektar grafa", Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, Osijek, 2018. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:126:517123

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:126:517123
Prijavite se u repozitorij kako biste mogli spremiti objekt u svoju listu.
Podaci o radu
NaslovSpektar grafa
Naslov (engleski)Spectar of Graph
AutorIva Petovari
MentorSnježana Majstorović (mentor)
Član povjerenstvaDarija Marković (predsjednik povjerenstva)
Član povjerenstvaSnježana Majstorović (član povjerenstva)
Član povjerenstvaDomagoj Ševerdija (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište Josipa Jurja Strossmayera u Osijeku
Odjel za matematiku
(Zavod za primijenjenu matematiku i računarstvo)
(Katedra za računarstvo i strojno učenje)
Osijek
Datum i država obrane2018-12-07, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Diskretna i kombinatorna matematika
Sažetak
Na temelju poznavanja nekih ili svih svojstvenih vrijednosti matrice susjedstva grafa možemo zaključiti nešto o strukturnim svojstvima kao što su bipartitnost, regularnost, grupa automorfizama, dijametar i kromatski broj. Također, informacije o tim svojstvima nam mogu ukazati na svojstva spektra. Proučavajući skup svih elementarnih grafova sadržanih u danom grafu, koji se sastoje od ciklusa i potpunog grafa s dva vrha, možemo izračunati koeficijente karakterističnog polinoma grafa te na temelju toga odrediti svojstvene vrijednosti matrice susjedstva. Iz matrice susjedstva i njezinih potencija možemo odrediti broj šetnji određene duljine u danome grafu. Istu informaciju možemo dobiti i koristeći svojstvene vrijednosti i komponente svojstvenih vektora ili koristeći karakteristične polinome grafa i njegovog komplementa. Poznati su nam spektri nekih posebnih tipova grafova, kao što su regularni grafovi stupnja jedan, potpun graf, potpun bipartitan graf, potpun multipartitan graf, put i ciklus. Graf je bipartitan ako i samo ako je njegov spektar simetričan s obzirom na nulu. Također, ako je najveća svojstvena vrijednost povezanog grafa jednaka njegovoj negativnoj najmanjoj svojstvenoj vrijednosti, graf je bipartitan. Za dokazivanje regularnosti grafa, dovoljno je provjeriti sumu kvadrata svojstvenih vrijednosti. Broj različitih svojstvenih vrijednosti matrice susjedstva daje nam gornju granicu za grafov dijametar te opisuje grupu automorfizama grafa. Na temelju poznavanja najmanje i najveće svojstvene vrijednosti, možemo dobiti donju i gornju granicu za kromatski broj grafa.
Sažetak (engleski)
By knowing some or all of the eigenvalues of the adjacency matrix of graph, we can conclude something about structural properties such as bipartitness, regularity, group of automorphisms, diameter and chromatic number. Also, information about these properties can point to the properties of graph spectra. By studying the set of all elementary graphs contained in the graph, which consists of a cycle and a complete graph with two vertices, we can calculate coefficients of the characteristic polynomial of a graph and thus determine the eigenvalues. From the adjacency matrix and its powers we can determine the number of walks of a certain length in the graph. The same information can also be obtained by using the eigenvalues and components of the eigenvectors, or by using characteristic polynomials of a graph and its complement. We know the spectra of some special types of graphs, such as regular graphs of degree one, complete graph, complete bipartite graph, complete multiparty graph, path and cycle. The graph is bipartite if and only if its spectrum is symmetric with respect to zero. Also, if the largest eigenvalue of a connected graph is equal to its negative smallest eigenvalue, the graph is bipartite. To prove the regularity of the graph, it is sufficient to check the sum of the squares of the eigenvalues. The number of different eigenvalues of the adjaceny matrix gives us the upper bound for the graph’s diameter and describes a group of automorphisms. By knownig the smallest and the largest eigenvalue, we can obtain lower and upper bounds for the graph’s chromatic number.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:126:517123
Studijski programNaziv: Matematika i informatika
Vrsta studija: sveučilišni
Stupanj studija: integrirani preddiplomski i diplomski
Akademski / stručni naziv: magistar/magistra edukacije matematike i informatike (mag. educ. math. et inf.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2018-12-11 07:07:55