Diskret matematik

Vad är en graf?
Vad har ett kopplingsschema och en vägkarta gemensamt? Jo, båda kan beskrivas som ett antal sammanbundna punkter. Det kan vara vägkorsningar eller lödpunkter sammanbundna av vägar eller ledningstrådar. Huvudsaken är att man kan beskriva båda schematiskt med en enkel bild. Denna förenklade bild kan man sedan studera och försöka hitta egenskaper hos. Till exempel kan man fråga sig om man kan ta sig från en punkt till varje annan punkt genom att endast gå längs de sammanbindande linjerna/vägarna eller om det alltid finns tillräckligt många slingor så att man kan räkna ut strömmen i sin uppkoppling av batterier och motstånd.

Exempel på grafer

Eftersom många av egenskaperna hos både det elektriska nätverket och det nätverk av bilvägar som vägkartan beskriver bestäms av hur de olika delarna är sammankopplade är den förenklade bilden intressant att studera. Denna förenklade bild kallas för en graf. Rent formellt består den av ett antal hörn, noder eller punkter, som förbinds med linjer, kanter eller bågar, för att bara nämna några synonymer i svenskan. Grafteoretiska modeller används med framgång i kemi, lingvistik, statistisk mekanik, operationsanalys (flöden i nätverk, schemaläggning), datalogi etc. för att ge en gripbar beskrivning av verkligheten. Grafer är något förenklat (minst sagt) den diskrete matematikerns legoblock.

Kombinavadå?
Kombinatorik kan man enkelt säga svarar på frådan "På hur många sätt"? Till exempel: På hur många sätt kan man slå sju med två sexsidiga tärningar? Många har i skolan stött på kombinatorik när man sysslat med klassisk sannolikhetslära, men kombinatorik kan användas i betydligt fler områden. För att endast nämna ett par: försöksuppläggning, geometri, grafteori och spelteori.

Upp

Nästa sida