grafo orientato con indegree massimo di un vertice

Question

stavo cercando di guardare alcune applicazioni del flusso di rete quando mi sono imbattuto in questo problema:

Cominciamo con un grafo orientato, G = (V,E). Abbiamo bisogno di aggiungere più spigoli al grafico tale che abbiamo \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both. cioè, vogliamo aggiungere più spigoli al grafico in modo che ogni coppia di vertici nel grafico sia collegata l'una all'altra (sia con un fronte uscente che con un bordo in entrata ma non con entrambi). Quindi, in totale avremo i bordi |V||V-1|/2. Mentre creiamo questo grafico, dobbiamo assicurarci che l'indegree di un dato vertice, ad esempio w, sia il massimo tra tutti i vertici del grafico (se possibile, dato il grafico originale). Si noti che non è possibile modificare l'orientamento dei bordi nel grafico originale.

Sto cercando di risolverlo utilizzando il flusso di rete creando una rete senza vertice w (e con 2 nuovi vertici per origine, s e sink, t). Ma non sono sicuro di come rappresentare le capacità e la direzione del flusso nel nuovo grafico in modo da semplificare il problema al flusso di rete al fine di trovare gli orientamenti dei bordi nel grafico. Forse quello che sto facendo è sbagliato, ma ho appena scritto se qualcuno potrebbe trarne un suggerimento.

Answer 1

Quando si attacca questo tipo di problema, tendo a scrivere un programma matematico e quindi a massaggiarlo. Chiaramente, dovremmo orientare tutti i bordi mancanti che coinvolgono w verso w. Sia d il risultante grado di w. Per tutti i distinti i, j, let x_{ij} = 1 se arc i-> j appare nella soluzione e lasciare x_{ij} = 0 se viene visualizzato l'arco j-> i.

forall j. sum_i x_{ij} <= k 
forall i <> j. x_{ij} = 1 - x_{ji} 
forall i <> j. x_{ij} in {0, 1} 

riscrittura da utilizzare x_{ij} solo se i < j.

(*) forall j. sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) <= k 
forall i < j. x_{ij} in {0, 1} 

Now (*) comincia ad assomigliare a vincoli di conservazione, come appare una volta negativamente e una volta positivamente ogni variabile. Cambiamo la disuguaglianza con un'uguaglianza.

(*) forall j. x_{si} + sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) = k 
       ^^^^^^           ^
forall i < j. x_{ij} in {0, 1} 
forall i. x_{si} >= 0 
^^^^^^^^^^^^^^^^^^^^^ 

Siamo quasi tutta la strada ad un LP flusso - abbiamo solo bisogno di pulire le costanti 1 e k. Ti permetterò di gestire il resto (comporta l'introduzione di t).