RSS Feed
Următoarea

Problema 107

21 Octombrie 2005

Rețea minimală


Următorul graf neorientat constă din 7 vârfuri și 12 laturi cu o pondere totală de 243.


Același graf poate fi reprezentat folosind matricea de mai jos.

    ABCDEFG
A-161221---
B16--1720--
C12--28-31-
D211728-181923
E-20-18--11
F--3119--27
G---231127-

Totuși, e posibil să optimizezi rețeaua îndepărtând unele laturi și asigurându-te că toate punctele rămân conectate. Graful care atinge un nivel maxim de economisire e afișat mai jos. Are o pondere de 93, reprezentând o economisire de 243 − 93 = 150 comparativ cu graful original.


Folosind network.txt (click dreapta și 'Save Link/Target As...'), un fișier text de 6K care conține un graf cu 40 de vârfuri reprezentat sub forma unei matrici, găsește nivelul maxim de economisire care poate fi atins prin îndepărtarea laturilor care sunt în plus astfel încât graful să rămână conectat.


Tag-uri:

>> Vezi problema originală <<