UNF Matematik Camp 2017

Matematisk uge i sommerferien med fuld power på faglighed og sammenhold

Grafteori

Du kender sikkert mange eksempler på grafer uden at vide det. I bund og grund er en graf bare en samling af knuder og forbindelser mellem knuder. Så for eksempel kunne man tænke på knuderne i et trafiksystem som lyskryds, og på forbindelserne som veje. Alternativt kunne man tænke på knuderne som mennesker, og på forbindelserne mellem mennesker som venskaber. I grafteori studerer man alle systemer som kan beskrives med knuder og forbindelser. Det er selvfølgelig en simplificering af verden at stille det op som en graf, men historisk har denne simplificering ofte båret frugt.

Et klassisk problem i grafteori er farvning. Givet en graf forsøger man at vælge en farve til hver knude, således at ingen knuder med samme farve er forbundet. Du kan se det som, at en gruppe piger gerne vil til fest, men ingen vil have samme farve kjole på som deres veninder. Spørgsmålet i vores forløb er, hvor få forskellige farver man kan nøjes med.

Graf nr. 1 (Foto: UNF)

Graf nr. 2 (Foto: UNF)