Kombinatorična teorija matrik
delo diplomskega seminarja
Povzetek
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.
Ključne besede
(0, 1)-matrika;matrika sosednosti;spekter grafa;incidenčna matrika;Laplaceova matrika;kompleksnost grafa;
Podatki
| Jezik: | Slovenski jezik |
|---|---|
| Leto izida: | 2020 |
| Tipologija: | 2.11 - Diplomsko delo |
| Organizacija: | UL FMF - Fakulteta za matematiko in fiziko |
| Založnik: | [V. Drobnič] |
| UDK: | 519.1:512.64 |
| COBISS: |
58842371
|
| Št. ogledov: | 1720 |
| Št. prenosov: | 127 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Angleški jezik |
|---|---|
| Sekundarni naslov: | Combinatorial matrix thoery |
| Sekundarni povzetek: | 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. |
| Sekundarne ključne besede: | (0, 1)-matrix;adjacency matrix;graph spectrum;incidence matrix;Laplacian matrix;graph complexity; |
| Vrsta dela (COBISS): | Delo diplomskega seminarja/zaključno seminarsko delo/naloga |
| Študijski program: | 0 |
| Konec prepovedi (OpenAIRE): | 1970-01-01 |
| Komentar na gradivo: | Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja |
| Strani: | 28 str. |
| ID: | 12039032 |
Priporočena dela: