Grafteori

I en lukket eulertur starter man på en given knude og går netop 1 gang ad hver kant til man vender tilbage til udgangspunktet. I en åben eulertur gælder næsten det samme, borset fra at den knude, man ender på ikke er startknuden. Tænk på et rektangel, ABCD, med diagonaler AC og BD. Start i A. Man kan se, at man ikke kan gå netop én gang ad hvert liniestykke og nå tilbage til A. Man kan faktisk slet ikke gå hele turen. Det hænger sammen med at der er 3 kanter til hver kunde. Går man f.eks fra A til B og videre til C, så bruger man AB og BC, og så er der kun BD tilbage ved B. Derfor skal en komplet åben eulertur ende i B. Fra C kan man gå til A eller D. Vælger man at gå til D, kan man gå til A og derfra til C, men her ender turen ude at man kan ende den i B. Man kan også vølge at gå fra C til A og så videre til D. Her der så muligheden at gå til B eller D, men så mangler der en side. Tilføjer man en kant, der går fra B til C, kan der gennemføres en åben eulertur. Tilføjer men yderligere en kant fra A til D, kan man gennemføre en lukket eulertur.

I nogle grafer er det muligt at finde en Hamiltonkreds. Du skriver her "kun én gang", det skal være "netop én gang".  Der er en udmærket gennemgang her:

https://en.wikipedia.org/wiki/Hamiltonian_path

Jeg kan ikke afgøre, om man kan have en Hamiltonvej, der ender et andet sted end den starter. Jeg vil tro, det er muligt.

At en graf er sammenhængende vil sige, at vælger man to vilkårlige knuder, er der altid en vej fra den ene til den anden. Man kan have en graf med 5 knuder, hvor knude 1 og 2 har en fælles kant og knuder 3, 4 og 5 er forbundet med hinanden med to kanter. Denne graf er ikke sammenhængende, da der f.eks ikke findes en vej fra 1 til 5.

Et træ er en sammenhængende graf, hvor der ikke er nogen cykliske veje. Mellem to knuder er der så én og kun én vej. Når man arbejder med træer, udnævner man ofte en af knuderne til at være roden R. Man tegner så træet med roden øverst. Lidt nedenfor på tegningen tegner man de knuder, der har en kant til R. Disse knuder betegnes somme tider som R's døtre. Under denne række tegnes en ny række knuder med kanter til døtrene. Hver knude i denne række har en kant til netop én i rækken ovenfor. Sådan fortsætter man nedad. Der er ingen kanter mellem knuder på samme række.