grafteori

Grafteori är det område inom matematiken som undersöker egenskaper hos grafer. En graf är en mängd punkter, kallade noder eller hörn, sammanbundna med linjer, kallade bågar eller kanter. Anledningen till att man valt orden noder och bågar eller kanter och hörn istället för punkter och linjer är att kanter och hörn saknar de vanliga euklidiska egenskaperna för punkter och linjer. Man kan lägga flera punkter på samma linje, men en kant kan bara gå mellan max två hörn. Kanten kan dessutom gå tillbaka till samma hörn. Den kallas då loop. Antalet kantändar som ansluter till samma hörn kallas hörnets grad. Det är möjligt att flera kanter går mellan samma par av hörn. Det kallas multipla kanter. En väg i en graf är en sekvens av noder sådan att det från varje nod (förutom möjligen den sista) i sekvensen finns en båge till nästa nod i sekvensen.