Osnovno o matroidih

diplomsko delo

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2021
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[M. Drvarič]
UDK:	004:519.1(043.2)
COBISS:	76899075
Št. ogledov:	693
Št. prenosov:	42
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Matroid basics
Sekundarni povzetek:	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.
Sekundarne ključne besede:	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;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	38 str.
ID:	13377264