Download
PDF 426.76 KB
master's thesis
56   12
Spectar of Graph
Iva Petovari (2018)
Josip Juraj Strossmayer University of Osijek
Department of Mathematics
Chair of Applied Mathematics
Computer Science Research Group
Cite this document

Petovari, I. (2018). Spektar grafa (Master's thesis). Retrieved from https://urn.nsk.hr/urn:nbn:hr:126:517123

Petovari, Iva. "Spektar grafa." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2018. https://urn.nsk.hr/urn:nbn:hr:126:517123

Petovari, Iva. "Spektar grafa." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2018. https://urn.nsk.hr/urn:nbn:hr:126:517123

Petovari, I. (2018). 'Spektar grafa', Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, accessed 21 November 2019, https://urn.nsk.hr/urn:nbn:hr:126:517123

Petovari I. Spektar grafa [Master's thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics; 2018 [cited 2019 November 21] Available at: https://urn.nsk.hr/urn:nbn:hr:126:517123

I. Petovari, "Spektar grafa", Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, Osijek, 2018. Available at: https://urn.nsk.hr/urn:nbn:hr:126:517123

Metadata
TitleSpektar grafa
Title (english)Spectar of Graph
AuthorIva Petovari
MentorSnježana Majstorović (mentor)
Committee memberDarija Marković (predsjednik povjerenstva)
Committee memberSnježana Majstorović (član povjerenstva)
Committee memberDomagoj Ševerdija (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Department of Mathematics
(Chair of Applied Mathematics)
(Computer Science Research Group)
Osijek
Defense date and country2018-12-07, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Discrete and Combinatorial Mathematics
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:126:517123
Study programmeTitle: Mathematics and Computer Science
Study programme type: university
Study level: integrated undergraduate and graduate
Academic / professional title: magistar/magistra edukacije matematike i informatike (magistar/magistra edukacije matematike i informatike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
Created on2018-12-11 07:07:55