Kombinatorična teorija matrik : delo diplomskega seminarja

Drobnič, Vid (author), 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.

• Language: Slovenian
• Keywords: (0, 1)-matrika, matrika sosednosti, spekter grafa, incidenčna matrika, Laplaceova matrika, kompleksnost grafa
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2020
• PID: 20.500.12556/RUL-120182
• UDC: 512.64
• COBISS.SI-ID: 58842371
• Publication date in RUL: 17.09.2020

Secondary language

• Language: English
• Title: Combinatorial matrix thoery

Abstract

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.

• Keywords: (0, 1)-matrix, adjacency matrix, graph spectrum, incidence matrix, Laplacian matrix, graph complexity