Osnovno o matroidih

diplomsko delo

Marko Drvarič (Author), Riste Škrekovski (Mentor)

Abstract

Matroidi so struktura v kombinatoriki, ki jo je prvi predstavil Hassler Whitney leta 1935, pri kateri se pojme kot so neodvisna mnozica, cikel, baza, rang, minor, dual in druge naravno posplosi in uporablja. Matroide lahko deniramo na vec nacinov, pri tem pa izhajamo predvsem iz terminologije uporabljene v teoriji grafov in linearne algebre. Glede na to, kako matroide deniramo, jih lahko uporabimo pri razlicnih kombinatoricno-optimizacijskih problemih, kot sta problem pakiranja in pokritja ter pozresna metoda.

Keywords

graf;vektor;linearna algebra;neodvisnost;računalništvo in informatika;računalništvo in matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2021
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[M. Drvarič]
UDC:	004:519.1(043.2)
COBISS:	76899075
Views:	693
Downloads:	42
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Matroid basics
Secondary abstract:	Matroids are a combinatorical structure, rst introduced by Hassler Whitney in 1935, that generalizes and uses notions such as independent set, cycle, base, rank function, minor, duality and others. Matroids can be dened in dierent ways, mostly using terminology used in graph theory and linear algebra. Based on the denition used, we can use matroids in a variety of problems from the elds of combinatorics and optimization, such as the packing and covering problems, as well as the greedy method.
Secondary keywords:	graph;vector;linear algebra;independency;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Kombinatorika (matematika);Linearna algebra;Teorija grafov;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	38 str.
ID:	13377264