Johnsonovi in Kneserjevi grafi

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2014
Izvor:	Ljubljana
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL PEF - Pedagoška fakulteta
Založnik:	[S. Pintar]
UDK:	519.17(043.2)
COBISS:	10045257
Št. ogledov:	1219
Št. prenosov:	160
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Johnson and Kneser graphs
Sekundarni povzetek:	This graduation paper deals with the so-called J-graph family and two of its subfamilies, the Johnson graphs and the Kneser graphs. These graph families are well known and their members have some important properties. For instance, they are very symmetric: the Johnsons graphs are even distance-transitive and therefore very interesting for researches. In this graduation paper we first present some basic properties of these graph families, their degree, connectedness, regularity and vertex-, edge- and arc-transitivity. Later we focus on some of the more complex properties. We determine the diameter of Johnson graphs and show that they are distance-transitive and hamilton connected. We determine the girth of the Kneser graphs and their chromatic number. Even though matematicians have been studying these graph families for quite a while now, a lot of questions remain unanswered. At the end of this graduation paper we present one of the more interesting ones.
Sekundarne ključne besede:	mathematics;matematika;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. Ljubljana, Pedagoška fak., Matematika in fizika
Strani:	VIII, 58 str.
Vrsta dela (ePrints):	thesis
Naslov (ePrints):	Johnsonovi in Kneserjevi grafi
Ključne besede (ePrints):	Johnsonov graf
Ključne besede (ePrints, sekundarni jezik):	Johnson graph
Povzetek (ePrints):	To diplomsko delo obravnava družino tako imenovanih J-grafov in dve njeni poddružini, Johnsonove in Kneserjeve grafe. Gre za zelo znane družine grafov, ki imajo nekaj pomembnih lastnosti. So, na primer, zelo simetrični - Johnsonovi grafi so tako celo razdaljno tranzitivni in jih kot takšne zelo radi študiramo. V diplomskem delu najprej raziščemo najosnovnejše lastnosti teh družin grafov, na primer red grafa, povezanost, regularnost ter točkovno, povezavno in ločno tranzitivnost, nato pa se posvetimo tudi nekaterim bolj zahtevnim. Tako določimo premer Johnsonovih grafov in pokažemo, da so razdaljno tranzitivni in hamiltonsko povezani. Določimo tudi ožino Kneserjevih grafov in njihovo kromatično število. Čeprav so vse te družine že nekaj časa pod drobnogledom matematikov, še kar nekaj vprašanj ostaja odprtih. Na koncu diplomskega dela predstavimo eno izmed bolj zanimivih.
Povzetek (ePrints, sekundarni jezik):	This graduation paper deals with the so-called J-graph family and two of its subfamilies, the Johnson graphs and the Kneser graphs. These graph families are well known and their members have some important properties. For instance, they are very symmetric: the Johnsons graphs are even distance-transitive and therefore very interesting for researches. In this graduation paper we first present some basic properties of these graph families, their degree, connectedness, regularity and vertex-, edge- and arc-transitivity. Later we focus on some of the more complex properties. We determine the diameter of Johnson graphs and show that they are distance-transitive and hamilton connected. We determine the girth of the Kneser graphs and their chromatic number. Even though matematicians have been studying these graph families for quite a while now, a lot of questions remain unanswered. At the end of this graduation paper we present one of the more interesting ones.
Ključne besede (ePrints, sekundarni jezik):	Johnson graph
ID:	8328001