Naslov Hallov teorem Naslov (engleski) Hall's theorem Autor Jelena Mišerić Mentor Slaven Kožić (mentor)Član povjerenstva Slaven Kožić (predsjednik povjerenstva)Član povjerenstva Marko Tadić (član povjerenstva)Član povjerenstva Ozren Perše (član povjerenstva)Član povjerenstva Nela Bosner (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2020-09-28, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Sažetak U ovom radu cilj je bio dokazati i vidjeti primjene jednog od važnijih teorema iz područja kombinatorike, Hallovog teorema. U prvom dijelu rada iskazana je njegova kombinatorna formulacija i ekvivalencija u smislu teorije grafova i sparivanja te su dana četiri različita dokaza Hallovog teorema. Prvi iskaz teorema govori o nužnom i dovoljnom uvjetu za postojanje transverzale danih konačnih skupova. Jednostavnom generalizacijom dolazi se do iskaza Hallovog teorema u smislu teorije grafova koji govori o nužnom i dovoljnom uvjetu za postojanje potpunog sparivanja u bipartitnom grafu. Na kraju drugog poglavlja iskazane su i neke posljedice iz područja kombinatorike, teorije skupova, teorije grupa i linearne algebre. Nadalje, u posljednjem poglavlju smo pokazali da je on samo jedan u nizu ekvivalentnih teorema čija primjena se širi na mnoga područja matematike pa je i motivacija koju smo vidjeli na početku rada raznolika. Medu ekvivalentne teoreme pripadaju osim Hallovog još Koenigov, Dilworthov, Mengerov, Birkhoff-Von Neumannov teorem i drugi. U radu su iskazani i dokazani navedeni teoremi i prikazana je njihova primjena. Vidjeli smo da objekti koji se promatraju u tim teoremima sežu od jednostavnih grafova (Mengerov i Koenigov teorem), binarnih matrica (Koenigov teorem) i dvostruko stohastičih matrica (Birkhoff-Von Neumannov teorem) do parcijalno uredenih skupova (Dilworthov teorem). Upoznali smo se i s latinskim pravokutnicima, još jednom specifičnom vrstom matrica, te smo pokazali da je Hallov teorem zaslužan za dokaz jednog od važnijih teorema o latinskim pravokutnicima.
Sažetak (engleski) The aim of this thesis was to prove and present the applications of one of the central theorems in the field of combinatorics, Hall’s theorem. Through the first part of the thesis we have expressed its combinatorial formulation, equivalence in terms of graph theory and matching and provided four different proofs. The first statement of the theorem gives the necessary and suficient condition for the existence of a system of distinct representatives of given sets. A simple generalization leads to the statement of Hall’s theorem in terms of graph theory, which speaks of a necessary and suficient condition for the existence of complete matching in a bipartite graph. At the end of the second chapter, several consequences from the field of combinatorics, set theory, group theory and linear algebra are presented. Furthermore, in the last chapter we have shown that Hall’s theorem is one in a sequence of equivalent theorems whose application extends to many areas of mathematics, so the motivation we saw at the beginning of the paper is diverse. Among the equivalent theorems, in addition to Hall’s theorem, there are Koenig’s, Dilworth’s, Menger’s, Birkhoff-Von Neumann theorem, and others. These theorems are stated and proved in this thesis and their application is presented. We have seen that the objects observed in these theorems vary from simple graphs (Menger’s and Koenig’s theorem), binary matrices (Koenig’s theorem) and doubly stochastic matrices (Birkhoff-Von Neumann theorem) to partially ordered sets (Dilworth’s theorem). We were also introduced to Latin rectangles, another specific type of matrix, and have shown that Hall’s theorem is responsible for proving one of the most important theorems in Latin rectangles.
Ključne riječi
bipartitni graf
kombinatorika
teorija skupova
teorija grupa
linearna algebra
Koenigov teorem
Dilworthov teorem
Mengerov teorem
Birkhoff-Von Neumannov teorem
Ključne riječi (engleski)
bipartite graph
combinatorics
set theory
group theory
linear algebra
Koenig’s theorem
Dilworth’s theorem
Menger’s theorem
Birkhoff-Von Neumann theorem
Jezik hrvatski URN:NBN urn:nbn:hr:217:952118 Studijski program Naziv: Računarstvo i matematika Vrsta resursa Tekst Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2021-03-01 13:18:00
