Opgaver i anvendelse af grafer (og sprogteori)

Opgaver i anvendelse af grafer
Opgave 1

Opret den ikke-retningsbestemte, vægtede graf i en adjacency-matrix repræsentation.

Opgave 2

Opret den retningsbestemte, vægtede graf - anvend eventuelt en adjacency-list repræsentation.

Opgave 3

Lav et program, der ved hjælp af datastrukturen graf kan repræsentere en vejlængdetabel for Fyn.

	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
1. Assens		42	36	61	72	38	34	68	39	64
2. Bogense	42		63	52	66	30	30	62	32	75
3. Fåborg	36	63		60	51	74	71	47	38	27
4. Kerteminde	61	52	60		24	69	70	19	22	53
5. Knudshoved	72	66	51	24		80	81	4	34	37
6. Lillebæltsbroen	38	30	74	69	80		4	76	47	87
7. Middelfart	34	30	71	70	81	4		77	48	88
8. Nyborg	68	62	47	19	4	76	77		30	33
9. Odense	39	32	38	22	34	47	48	30		43
10. Svendborg	64	75	27	53	37	87	88	33	43

(Kilde: Danmark 1:100000 Topografisk Atlas, Geodætisk Institut, København 1982)

Udarbejd en syntaks, der kan anvendes ved indlæsning af tabellens data fra en tekstfil. Udarbejd en tekstfil, der overholder den definerede syntaks, og lad programmet indlæse den. Lav i den forbindelse en leksikalsk analyse, der kan afvise en tekstfil med en forkert syntaks. Er syntaksen korrekt indsættes data i en graf.

Lav kontrol af, at data er indsat korrekt i grafen, f.eks. gennem forespørgsel på om et stednavn findes eller om afstanden mellem to stednavne.

Udarbejd en algoritme, der løser "the traveling salesperson problem", således at man med start og slut i Odense besøger samtlige byer i grafen og samtidig tilbagelægger den korteste samlede strækning.