Kombinatorična teorija matrik : delo diplomskega seminarja

Drobnič, Vid (avtor), Cigler, Gregor (mentor)

Delo opisuje nekatere osnovne rezultate kombinatorične teorije matrik. Kombinatorična teorija matrik je veja matematike, ki združuje kombinatoriko, teorijo grafov in linearno algebro. V prvem delu diplomske naloge si podrobneje ogledamo algebraične lastnosti (0, 1)-matrik. Klasičen problem tlakovanja pravokotnikov zapišemo z matrično enačbo in s pomočjo lastnosti (0, 1)-matrik rešimo zanimiv kombinatorični primer. V drugem delu diplomske naloge graf predstavimo z matriko sosednosti ter incidenčno matriko. Izpeljemo povezavo med tema dvema matrikama in definiramo Laplaceovo matriko grafa. Povežemo nekatere lastnosti grafa z algebraičnimi lastnostmi matrike sosednosti ter incidenčne matrike. Na koncu se podrobneje posvetimo Laplaceovi matriki grafa in izpeljemo formulo za izračun števila vpetih dreves v grafu.

• Jezik: Slovenski jezik
• Ključne besede: (0, 1)-matrika, matrika sosednosti, spekter grafa, incidenčna matrika, Laplaceova matrika, kompleksnost grafa
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2020
• PID: 20.500.12556/RUL-120182
• UDK: 512.64
• COBISS.SI-ID: 58842371
• Datum objave v RUL: 17.09.2020

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Combinatorial matrix thoery

Izvleček

This thesis describes some of the basic results of combinatorial matrix theory. Combinatorial matrix theory is a branch of mathematics that connects combinatorics, graph theory and linear algebra. The first part of the thesis deals with algebraic properties of (0, 1)-matrices. We reformulate an elementary problem in geometry in terms of matrices and solve an interesting combinatorial problem with the help of the properties of (0, 1)-matrices. In the second part of the thesis we represent a graph with its adjacency matrix and its incidence matrix. We derive a relation between the two matrices and define a Laplacian matrix of a graph. We connect properties of a graph with algebraic properties of its adjacency and incidence matrix. At the and we discuss Laplacian matrix of a graph and derive a formula for calculating the number of spanning trees in a graph.

• Ključne besede: (0, 1)-matrix, adjacency matrix, graph spectrum, incidence matrix, Laplacian matrix, graph complexity