---

Hej

Jeg forosøger at forstå, hvad "directed acyclic graph" dækker over.

Jeg har læst på http://mathworld.wolfram.com/AcyclicDigraph.html men fatter
ikke en bønne af det.

Er der nogen der kan forklare det i menneskesprog?

Mvh
Jimmy

---

"Jimmy" <nyhedsgruppe2001@SPAM.yahoo.co.uk> writes:

> Jeg har læst på http://mathworld.wolfram.com/AcyclicDigraph.html men fatter
> ikke en bønne af det.

En graf består af nogle punkter og nogle streger meller to punkter.

I en 'directed' graf har hver streg en retning.

En directed acyclic graph er en directed graph der ikke har nogen
cycler. Det vil sige at uanset hvilket punkt man starter i, så kan man
ikke ved at følge stregerne i retningen komme tilbage til
begyndelsespunktet.

--
Peter Makholm | Ladies and gentlemen, take my advice, pull down your
peter@makholm.net | pants and slide on the ice
http://hacking.dk | -- Sidney Freedman

---

Det er ikke en graf i folkeskole eller gymnasie forstand for det første.

Forestil dig et landkort
der er nogle byer som er små prikker
de kaldes 'knuder' i grafteori (nodes på engelsk. evt vertex)

imellem byerne er der nogle veje (rette linier)
de kaldes 'kanter' i grafteori (edges på engelsk)

så har du en graf

'directed' betyder at alle veje pludselig er ensrettede (pile på)
'orienteret' på dansk

så har du en directed graph

'acyclic' betyder blot at der ikke må være veje der til sammen kører i ring

acyclic directed graph


en kant kan desuden have en vægt. Hvis man laver en graf til at representere
et vejkort så kunne den vægt passende være afstanden mellem de to byer den
forbinder.

easy beasy