prikaz prve stranice dokumenta Pfaffijan i savršena sparivanja
  Preuzmi
PDF 298.4 KB
diplomski rad
Pfaffijan i savršena sparivanja
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2020. urn:nbn:hr:217:590683
Granić, Karla
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Granić, K. (2020). Pfaffijan i savršena sparivanja (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:590683

Granić, Karla. "Pfaffijan i savršena sparivanja." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2020. https://urn.nsk.hr/urn:nbn:hr:217:590683

Granić, Karla. "Pfaffijan i savršena sparivanja." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2020. https://urn.nsk.hr/urn:nbn:hr:217:590683

Granić, K. (2020). 'Pfaffijan i savršena sparivanja', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 26.11.2024., https://urn.nsk.hr/urn:nbn:hr:217:590683

Granić K. Pfaffijan i savršena sparivanja [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2020 [pristupljeno 26.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:590683

K. Granić, "Pfaffijan i savršena sparivanja", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2020. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:590683

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:590683
Podaci o radu
NaslovPfaffijan i savršena sparivanja
AutorKarla Granić
MentorVedran Krčadinac (mentor)
Član povjerenstvaVedran Krčadinac (predsjednik povjerenstva)
Član povjerenstvaSanja Varošanec (član povjerenstva)
Član povjerenstvaFilip Najman (član povjerenstva)
Član povjerenstvaMarko Erceg (č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 obrane2020-02-28, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
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.
Sažetak (engleski)
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.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:590683
Studijski programNaziv: Matematička statistika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2020-07-23 10:18:58