Simone Ohlsson: Fyrfärgssatsen och en introduktion till grafteori
Bachelor thesis presentation
Time: Thu 2022-06-02 10.00 - 11.00
Location: Kräftriket, house 6, room 306
Respondent: Simone Ohlsson
Abstract:
Målet med det här arbetet är att ge läsaren en introduktion till grafteori och grundläggande grafteoretiska begrepp där det huvudsakliga fokuset riktas mot färgläggning av grafer. Fyrfärgssatsen säger att en planär graf alltid kan färgläggas med fyra färger eller färre, den ursprungliga formuleringen handlade dock om färgläggning av kartor snarare en grafer. Beviset av fyrfägssatsen är omfattande och ryms inte inom ramen för denna uppsats. Istället återges de huvudsakliga id´eerna bakom beviset, där målet är att visa att det inte kan finnas något minimalt motexempel genom att hitta en oundviklig mängd av reducibla konfigurationer. En reducibel konfiguration kan inte ingå i ett minimalt motexempel och åtminstone en konfiguration från varje oundviklig mängd måste ingå i varje planär graf. Av detta följer att om en oundviklig mängd endast består av reducibla konfigurationer så kan det inte finnas något minimalt motexempel och satsen är bevisad. Aven färgläggning av grafer med två, tre och fem färger behandlas. Färgläggning med två och tre färger är möjlig för grafer med vissa specifika egenskaper medan färgläggning med fem färger gäller för en godtycklig planär graf. Avslutningsvis undersöks olika färgläggningsalgoritmer och vi kan konstatera att en och samma graf kan få olika färgläggningar beroende på vald algoritm.