Come osserva Evgeny nei commenti, questo è noto come maximum leaf spanning tree problem. Ho collegato l'articolo di Wikipedia al problema dei set dominanti connessi strettamente correlati, che è il problema di trovare un set minimo di vertici che (i) induca un sottografo collegato (ii) a soddisfare la proposizione che, per tutti gli altri vertici v , alcuni vertici nell'insieme sono adiacenti a v. I due problemi mostrati come equivalenti alla soluzione osservando che, dato uno spanning tree, possiamo costruire un set dominante collegato facendo cadere le foglie (i vertici con esattamente una connessione), e dato un set dominante collegato, possiamo estrarre un albero di copertura del sottografo indotto e attaccare gli altri vertici come foglie.
Sfortunatamente, entrambi i problemi sono NP-rigidi e rimangono NP-rigidi sotto una limitazione ai grafici planari. Non ho familiarità con la letteratura sul set dominante in particolare, ma la mia ipotesi è che ci siano tre angoli.
- Algoritmi/algoritmi di approssimazione esatti in tempo esponenziale "veloci".
- Algoritmi esatti che non sono sufficientemente veloci (ad es. Programmazione in interi) ma buoni nella pratica.
- Euristica.
# 1 può sembrare uno strano gruppo, ma ciò che tende ad accadere nella letteratura grafo planare è che gli algoritmi esatti vengono usate come subroutine all'interno degli algoritmi di approssimazione, spesso tramite una tecnica a causa Brenda Baker denominato mutevole. Una delle proprietà dei grafici planari è che un parametro chiamato treewidth è delimitato da O (sqrt (n)) invece di n, e ci sono programmi dinamici il cui esponente del tempo di esecuzione è una funzione della treewidth molto più piccola. Ad esempio, sulle griglie, è possibile eseguire una riga riga per riga D. Il macchinario di scomposizione dell'albero generalizza questo a grafici planari arbitrari.
È difficile consigliarti sul percorso migliore senza sapere come sono le istanze e forse anche senza sperimentare con loro. Probabilmente andrei con la porta # 2, ma non sono sicuro di come sarebbe una buona formulazione. La buona notizia è che la maggior parte della complessità algoritmica è astratta nella libreria del solutore che userete. Ecco una formulazione di qualità sconosciuta.
Per tutti i vertici v, cerchiamo x_v essere 1 se v è un non-foglia e 0 se v è una foglia. La parte set dominante è facile.
minimize sum_v x_v
subject to
for all v, sum_{w such that w = v or w ~ v} x_w >= 1
for all v, x_v in {0, 1}
Qui sto usando ~ per significare "è adiacente a". L'applicazione del vincolo di connettività è più complicata. L'approccio più semplice che posso pensare è quello di risolvere il programma intero così com'è, quindi cercare due vertici s e t che sono entrambi scelti ma non connessi nella soluzione, calcolare un separatore di vertici minimo U tra s e t tra i separatori non inclusi un vertice scelto, immettere un vincolo
(1 - x_s) + (1 - x_t) + sum_{v in U} x_v >= 1
e quindi riprovare.
Sarei più fiducioso su un approccio che utilizza in modo esponenziale molte variabili, ma potrebbe essere molto più difficile da implementare (generazione di righe e colonne). Scegli un vertice r che sarà forzato come non foglia (indovina o prova tutte le possibilità). C'è una variabile y_P per ogni percorso semplice P con r come endpoint.
minimize sum_v x_v
subject to
for all v, for all P having v as an interior vertex,
x_v >= y_P
for all v, sum_{P having v as an endpoint} y_P >= 1
for all v, x_v in {0, 1}
for all P, y_P in {0, 1}
Ti interessa ridurre al minimo il livello medio dell'intero albero di copertura o solo la riduzione al minimo del numero di nodi non foglia? – aportr
@jabolotai - Potresti definire cosa intendi per "il grado medio dell'intero albero di copertura"? – user200783
Se si confrontano due spanning tree e uno ha un vertice di grado 5 mentre l'altro è identico tranne che invece ha un vertice di grado 4, ne tratteresti uno come soluzione migliore, o li considereresti uguali? – aportr