Pfaffijan i savršena sparivanja

diplomski rad

• Autor: Karla Granić
• Mentor: Vedran Krčadinac (mentor)
• Član povjerenstva: Vedran Krčadinac (predsjednik povjerenstva)
• Član povjerenstva: Sanja Varošanec (član povjerenstva)
• Član povjerenstva: Filip Najman (član povjerenstva)
• Član povjerenstva: Marko 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 obrane: 2020-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: savršena sparivanja u grafu; Pfaffijan antisimetrične matrice; Kasteleynov rezultat
• Ključne riječi (engleski): perfect matchings in graphs; Pfaffian of a skew-symmetric matrix; Kasteleyn’s result
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:590683
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-07-23 10:18:58