Algoritmo di ricerca locale per partizione uniforme di grafo

[corsara73]

salve devo risolvere il seguente esercizio :
ho una partizione uniforme di grafo dove il numero di vertici è 10.
mi fornisce la matrice corrispondente a una data bipartizione del grafo : tale che la cardinalita di A sia uguale a quella di B
8 0 4 0 0
0 3 6 0 2
1 7 0 4 3
1 5 6 2 0
0 0 0 9 8

come di fa a determinare la matrice di adiacenza del grafo di cui sopra dalla quale è stata ricavata questa sottomatrice
corrispondente a una particolare partizione? E come si fa a ricavare la partizione stessa?

Grazie

[corsara73]

altro dato del problema : la somma dei pesi degli archi incidenti su ogni singolo nodo è 20 ed è uguale per tutti i nodi.

[hamming_burst]

Ciao,
non mi è chiaro cosa tu chieda da come lo hai esposto.
Cerchi un algoritmo di LS per ricavare questa matrice di adiacenza da quella che hai scritto?
Per il problema della bipartizione cmq ci sono alcuni algoritmi di LS.

Ma ora non riesco ad interpretare tale matrice delle corrispondenze...dove la hai presa?

[corsara73]

il testo dell'esercizio è questo

[lakers12]

cost(x)=I(x)+E(x)
sai che cost(x)=20 per tutti i nodi
inoltre sai che E(x) è uguale alla somma di tutti i costi esterni ed è data, ad esempio, per la prima riga, da 8+4=12 quindi il costo interno I(x) per la prima riga è 20-12=8 e così via per tutte le righe e le colonne...così hai completato costi interni ed esterni della matrice di sinistra. Il mio dubbio ora è la domanda 2.2 ...come faccio a sapere precisamente i nodi della partizione? qualcuno lo sa?