Syftet med den här uppsatsen är att undersöka graden av planäritet för kompletta multipartita grafer. Det primära resultatet som presenteras är en formel som kan användas för att nedåt begränsa det minsta antalet korsningar som behövs för att realisera en komplett bipartit graf indelad i m respektive n noder: cr(K_{m,,n}) >= q - 2p + 4, m >= n >= 2, där q = mn och p = m + n. Därutöver presenteras tabeller som med formeln som utgångspunkt uppskattar eller bestämmer det minsta antalet korsningar för alla kompletta multipartita grafer med sju noder eller mindre. Uppsatsen innehåller också en genomgång av några tidigare resultat, däribland Zarankiewicz uppställning av kompletta bipartita grafer samt en överblick över Crossing Number Inequality
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:oru-35367 |
| Date | January 2014 |
| Creators | Lissel, Erik |
| Publisher | Örebro universitet, Institutionen för naturvetenskap och teknik |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds