Kombinatorična teorija matrik
delo diplomskega seminarja
Abstract
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.
Keywords
(0, 1)-matrika;matrika sosednosti;spekter grafa;incidenčna matrika;Laplaceova matrika;kompleksnost grafa;
Data
| Language: | Slovenian |
|---|---|
| Year of publishing: | 2020 |
| Typology: | 2.11 - Undergraduate Thesis |
| Organization: | UL FMF - Faculty of Mathematics and Physics |
| Publisher: | [V. Drobnič] |
| UDC: | 519.1:512.64 |
| COBISS: |
58842371
|
| Views: | 1720 |
| Downloads: | 127 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| Secondary title: | Combinatorial matrix thoery |
| Secondary 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. |
| Secondary keywords: | (0, 1)-matrix;adjacency matrix;graph spectrum;incidence matrix;Laplacian matrix;graph complexity; |
| Type (COBISS): | Final seminar paper |
| Study programme: | 0 |
| Embargo end date (OpenAIRE): | 1970-01-01 |
| Thesis comment: | Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja |
| Pages: | 28 str. |
| ID: | 12039032 |
Recommended works: