| Område: | Diskret matematik | Emne: | Grafteori | Niveau: | A |
| Opgave/Titel: |
Du skal gøre rede for de begreber, der benyttes i grafteorien, lige som du skal formulere og bevise sætninger som knytter sig til denne.
Du skal desuden omtale, hvorledes grafteorien benyttes i forbindelse med løsning af firfarveproblemet. Følgende opgaver skal løses og indgå i din besvarelse, hvor du finder det passende: Opgave 1. Kontrollér, at Eulers polyederformel gælder for den graf der udgøres af et kvadratnet med n felter på hver led. Opgave 2. Tegn en dual graf til den fuldstændige graf K4. Opgave 3. På Sjælland er afstandene i km mellem nogle større byer: København – Næstved: 81 Roskilde – Næstved: 54 Korsør – Roskilde: 76 København – Roskilde: 31 Korsør – Næstved: 46 Vordingborg – Roskilde: 78 København – Korsør: 107 Vordingborg – Næstved: 29 Korsør – Vordingborg: 74 København – Vordingborg: 92 Konstruér et minimalt træ (skelet) der indeholder de 5 byer. |
||||
| Kilder: |
Jens Carstensen Grafteori Systime 1992 Karsten Dam Firfarveproblemet Systime 1990 Vagn Lundgaard Hansen Den geometriske dimension Nyt Nordisk Forlag Arnold Busck A/S 1989 Preben D. Vestergaard Løste og uløste matematiske problemer Aalborg Universitets forlag 1985 |
||||