Teorem o pakiranju krugova

master's thesis

• Title (english): The circle packing theorem
• Author: Nikolina Rašić
• Mentor: Tomislav Pejković (mentor)
• Committee member: Tomislav Pejković (predsjednik povjerenstva)
• Committee member: Zrinka Franušić (član povjerenstva)
• Committee member: Boris Širola (član povjerenstva)
• Committee member: Ozren Perše (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-12-02, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Američki matematičar William Paul Thurston revidirao je 1970-ih teorem njemačkog matematičara Paula Koebea iz 1930-ih koji je veza između planarnih grafova i pakiranja krugova. Koebeov teorem je postao temelj za danas poznati Koebe-Andreev-Thurstonov teorem, još znan pod imenom Teorem o pakiranju krugova. Jedan od iskaza teorema o pakiranju krugova glasi: Za svaki planarni graf G sa skupom vrhova \(V=\{v_1,...,v_n \}\) i skupom bridova E, postoji pakiranje \(\mathcal{C}=\{C_1,...,C_n\}\) od n (ne nužno sukladnih) krugova u ravnini sa svojstvom da se \(C_i\) i \(C_j\) dodiruju ako i samo ako je \(\{v_i, v_j\}\in E\), za svaki \(i,j\in \{1,...,n\}\), \(i \neq j\). Ovaj diplomski rad podijeljen je na četiri poglavlja. U prvom poglavlju navodimo ona preslikavanja ravnine potrebna za dokaz Apolonijevog teorema i teorema o pakiranju krugova. U drugom poglavlju navodimo iskaz i dokaz Apolonijevog teorema kao jedan primjer pakiranja krugova prije nego li se uopće promatrao taj problem. Kako je Koebeov teorem poveznica planarnih grafova i pakiranja krugova, u trećem poglavlju navodimo osnovne pojmove teorije grafova. U posljednjem poglavlju navodimo nekoliko iskaza teorema o pakiranju krugova te jedan kombinatorni dokaz proveden u tri koraka.

Abstract (english)

American mathematician William Paul Thurston revised in the 1970s a theorem of German mathematician Paul Koebe from the 1930s connecting planar graphs and circle packings. Koebe’s theorem became the foundation for the Koebe-Andreev-Thurston theorem, also known as The circle packing theorem. One statement of the circle packing theorem is the following. Given any finite simple planar graph G = (V; E), with the set of vertices \(V=\{v_1,...,v_n \}\), there exist n circles in the plane, \(\mathcal{C}=\{C_1,...,C_n\}\), with disjoint interiors, such that \(C_i\) is tangent to \(C_j\) if and only if \(\{v_i, v_j\}\in E\). This graduate thesis is divided into four chapters. In the first one, we introduce those transformations of the plane needed to prove Apollonius’ theorem and the circle packing theorem. In the second chapter, we present the statement and proof of Apollonius’ theorem as one example of circle packing before this problem was even observed. As Koebe’s theorem is a connection between planar graphs and circle packings, in the third chapter we list some basic concepts of graph theory. In the last chapter, we present several statements of the circle packing theorem and one combinatorial proof conducted in three steps.

• Keywords: William Paul Thurston; Paul Koebe; Koebe-Andreev-Thurstonov teorem; Apolonijev teorem; teorija grafova
• Keywords (english): William Paul Thurston; Paul Koebe; Koebe-Andreev-Thurston theorem; Apollonius theorem; graph theory
• Language: croatian
• URN:NBN: urn:nbn:hr:217:407291
• Study programme: Title: Mathematics Education; specializations in: Mathematics Education; Course: Mathematics Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike (magistar/magistra edukacije matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-12-16 12:49:47