Grafer med maksimal grad d, diameter k og lille defekt
Oversat titel
Graphs with maximal degree d, diameter k and small defect
Forfatter
Sillasen, Anita Abildgaard
Semester
4. semester
Uddannelse
Udgivelsesår
2009
Antal sider
88
Abstract
Specialet fra 10. semester i diskret matematik undersøger grad/diameter-problemet: hvor store grafer (netværk af knuder og forbindelser) kan være, når man på forhånd fastsætter en maksimal grad d (hvor mange forbindelser en knude må have) og en diameter k (den længste afstand i antal trin mellem to knuder). En (d,k)-graf har n(d,k) knuder. Kapitel 1 giver en teoretisk øvre grænse for n(d,k) via Moore-grænsen M(d,k) og forklarer, hvorfor kun meget få (d,k)-grafer når denne grænse. Kapitel 2 viser, at der også findes meget få (d,k)-grafer med M(d,k) − 1 knuder. Derfor undersøger Kapitel 3 egenskaber ved (d,k)-grafer med M(d,k) − 2 knuder og beviser særligt, at der er meget få (3,k)-grafer med M(3,k) − 2 knuder. Kapitel 4 analyserer (3,k)-grafer med M(3,k) − 4 knuder og viser igen, at sådanne grafer er sjældne. Afslutningsvis præsenteres nogle af de største kendte (d,k)-grafer. Da mange af disse er Cayley-grafer (grafer konstrueret ud fra gruppeteori), gives en enkel metode til at bygge store Cayley-grafer, inden resultaterne samles i Kapitel 6.
This thesis in discrete mathematics examines the degree/diameter problem: how large graphs (networks of nodes and connections) can be when a maximum degree d (how many connections a node may have) and a diameter k (the longest distance in steps between two nodes) are fixed. A (d,k)-graph has n(d,k) nodes. Chapter 1 presents a theoretical upper bound for n(d,k) via the Moore bound M(d,k) and explains why very few (d,k)-graphs reach this bound. Chapter 2 shows that there are also very few (d,k)-graphs with M(d,k) − 1 nodes. Chapter 3 therefore studies properties of (d,k)-graphs with M(d,k) − 2 nodes and specifically proves that very few (3,k)-graphs have M(3,k) − 2 nodes. Chapter 4 analyzes (3,k)-graphs with M(3,k) − 4 nodes and again shows that such graphs are rare. Finally, the thesis presents some of the largest known (d,k)-graphs. Because many of these are Cayley graphs (graphs constructed from group theory), it outlines a simple way to build large Cayley graphs, before summarizing the results in Chapter 6.
[Dette resumé er genereret ved hjælp af AI]