WisFaq!

IJscotent

Oke, ik zit met een enorm dilemma. Ik heb een graaf met een aantal knopen. Je plaatst een ijscotent en ik heb al berekend dat als ik 4 verkooppunten neem dat ik dan iedereen kan bereiken, maar nu moet ik weten hoe het aantal knopen samenhangt met het aantal verkooppunten.Graag hulp.

Imp
18-7-2001

Antwoord

Eén woord: DIAMETER

Zoek maar eens met DIAMETER GRAPH

Diameter (Graph)
The length of the "longest shortest path" between two Vertices of a Graph. In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration.

Dus zoiets als "longest shortest path" d.w.z. het langste korte pad is bijvoorbeeld 8. Hoeveel verkooppunten heb je dan nodig?

Zoek ook eens naar 'shortest path algoritm'.

WvR
18-7-2001