prikaz prve stranice dokumenta Pfaffijan i savršena sparivanja
  Download
PDF 298.4 KB
master's thesis
Pfaffijan i savršena sparivanja
Zagreb: University of Zagreb, Faculty of Science, 2020. urn:nbn:hr:217:590683
Granić, Karla
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Granić, K. (2020). Pfaffijan i savršena sparivanja (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:590683

Granić, Karla. "Pfaffijan i savršena sparivanja." Master's thesis, University of Zagreb, Faculty of Science, 2020. https://urn.nsk.hr/urn:nbn:hr:217:590683

Granić, Karla. "Pfaffijan i savršena sparivanja." Master's thesis, University of Zagreb, Faculty of Science, 2020. https://urn.nsk.hr/urn:nbn:hr:217:590683

Granić, K. (2020). 'Pfaffijan i savršena sparivanja', Master's thesis, University of Zagreb, Faculty of Science, accessed 17 May 2024, https://urn.nsk.hr/urn:nbn:hr:217:590683

Granić K. Pfaffijan i savršena sparivanja [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2020 [cited 2024 May 17] Available at: https://urn.nsk.hr/urn:nbn:hr:217:590683

K. Granić, "Pfaffijan i savršena sparivanja", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2020. Available at: https://urn.nsk.hr/urn:nbn:hr:217:590683

Metadata
TitlePfaffijan i savršena sparivanja
AuthorKarla Granić
MentorVedran Krčadinac (mentor)
Committee memberVedran Krčadinac (predsjednik povjerenstva)
Committee memberSanja Varošanec (član povjerenstva)
Committee memberFilip Najman (član povjerenstva)
Committee memberMarko Erceg (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2020-02-28, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
U ovom radu obradili smo savršena sparivanja u grafu i Pfaffijan antisimetrične matrice. U početku upoznajemo definiciju savršenog sparivanja i rezultate koji su nam potrebni za ostatak rada. Nakon toga pokazujemo kriterij za egzistenciju savršenog sparivanja u bipartitnom grafu i u proizvoljnom grafu. Opisujemo probabilistički algoritam koji pitanje egzistencije savršenog sparivanja rješava u polinomijalnom vremenu. Zatim utvrđujemo da permanenta matrice bisusjedstva bipartitnog grafa broji sva savršena sparivnja, međutim izračunavanje permanente je #P-potpun problem za kojeg nije poznat polinomijalni algoritam. U zadnjem dijelu rada obrađujemo Kasteleynov rezultat da u planarnom grafu možemo efikasno prebrojati sva savršena sparivanja, i to preko Pfaffijana antisimetrične matrice susjedstva grafa kojeg smo orijentirali na odgovarajući način.
Abstract (english)
This master thesis deals with perfect matchings in graphs as well as with the Pfaffian of a skew-symmetric matrix. The topic is introduced with the definition of perfect matchings and with results that are useful for later work. Then the criterion for existence of perfect matching is shown for bipartite graphs and the arbitrary graphs. We describe probabilistic algorithm which solves the existence problem of perfect matchings in polynomial time. In addition, it is determined that the permanent of the biadjacency matrix of a bipartite graph counts all perfect matchings. However, it turns out that the calculation of permanent is #P-complete problem for which polynomial algorithm isn’t known. Nevertheless, in the last part of the thesis we deal with Kasteleyn’s result that we can efficiently compute all perfect matchings in planar graphs through Pfaffian of adjacency matrix of the graph, which is oriented appropriately.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:590683
Study programmeTitle: Mathematical Statistics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2020-07-23 10:18:58