prikaz prve stranice dokumenta Niz stupnjeva grafa
  Download
PDF 7.68 MB
undergraduate thesis
Niz stupnjeva grafa
2019. urn:nbn:hr:126:857223
Begović, Dolores
Josip Juraj Strossmayer University of Osijek
Department of Mathematics
Chair of Applied Mathematics and Computer Science
Computer Science and Machine Learning Research Group

Cite this document

Begović, D. (2019). Niz stupnjeva grafa (Undergraduate thesis). Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics. Retrieved from https://urn.nsk.hr/urn:nbn:hr:126:857223

Begović, Dolores. "Niz stupnjeva grafa." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2019. https://urn.nsk.hr/urn:nbn:hr:126:857223

Begović, Dolores. "Niz stupnjeva grafa." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2019. https://urn.nsk.hr/urn:nbn:hr:126:857223

Begović, D. (2019). 'Niz stupnjeva grafa', Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, accessed 12 November 2024, https://urn.nsk.hr/urn:nbn:hr:126:857223

Begović D. Niz stupnjeva grafa [Undergraduate thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics; 2019 [cited 2024 November 12] Available at: https://urn.nsk.hr/urn:nbn:hr:126:857223

D. Begović, "Niz stupnjeva grafa", Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, Osijek, 2019. Available at: https://urn.nsk.hr/urn:nbn:hr:126:857223

Please login to the repository to save this object to your list.
Metadata
TitleNiz stupnjeva grafa
Title (english)Degree Sequence
AuthorDolores Begović
MentorSnježana Majstorović (mentor)
GranterJosip Juraj Strossmayer University of Osijek
Department of Mathematics
(Chair of Applied Mathematics and Computer Science)
(Computer Science and Machine Learning Research Group)
Osijek
Defense date and country2019-09-30, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Discrete and Combinatorial Mathematics
Abstract
Teorija grafova je od velikog značaja u različitim područjima znanosti. Jednostavni konačni grafovi predstavljaju značajnu vrstu grafova. U ovom završnom radu se razmatra niz stupnjeva konačnog jednostavnog grafa, pojam usko vezan uz osnovne elemente grafa, vrhove i bridove. Dokazana su dva najpoznatija kriterija kojima su dani nužni i dovoljni uvjeti da bi niz nenegativnih brojeva bio niz stupnjeva nekog grafa, teorem Havela i Hakima te teorem Erdosa i Gallai. Teorem Havela i Hakima je zasnovan na rezidualnom ostatku najvećeg elementa niza stupnjeva, a teoremom Erdosa i Gallai je dana najpoznatija eksplicitna karakterizacija niza stupnjeva. Na temelju teorema Havela i Hakima može se razviti algoritam kojim se utvrđuje predstavlja li niz nenegativnih brojeva niz stupnjeva nekog grafa. Razmatran je i pojam skupa stupnjeva grafa te dokazan teorem kojim se utvrđuje najmanji broj vrhova grafa među svim grafovima čiji je to skup stupnjeva. Razmatran je i niz stupnjeva grafa s predznacima te navedeni kriteriji da bi taj niz bio grafički niz.
Abstract (english)
Graph theory is of great importance in various elds of science. Simple nite graphs represent a signicant type of graph. This nal paper discusses the degree sequence of a nite simple graph, a concept closely related to the basic elements of a graph, i.e., vertices and edges. Two well-known criteria which give the necessary and sucient conditions for a sequence of nonnegative numbers to be a degree sequence of a graph have been proved, the Havel-Hakimi theorem and the Erd®s-Gallai theorem. The Havel-Hakimi theorem is based on the residual sequence of the largest element of a degree sequence and the Erd®s-Gallai theorem gives the most known explicit characterization of a degree sequence. Based on the Havel-Hakimi theorem, an algorithm can be developed to determine whether a set of nonnegative numbers is a degree sequence. The concept of a degree set of a graph was considered and a theorem was proved to determine the smallest number of vertices of a graph among all graphs of which it is a degree set. A degree sequence of a signed graph was considered and the criteria were specied to make the degree sequence a graphical sequence.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:126:857223
Study programmeTitle: University undergraduate study programme in mathematics
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) matematike (sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2019-10-15 07:59:37