Albero di copertura - Spanning tree

Un albero ricoprente (bordi pesanti blu) di un grafico a griglia

Nel matematica campo della teoria dei grafi , un albero ricoprente T di un grafo G è un sottografo che è un albero che include tutti i vertici di G . In generale, un grafo può avere diversi spanning tree, ma un grafo non connesso non conterrà uno spanning tree (vedi spanning tree sotto). Se tutti gli archi di G sono anche archi di un albero ricoprente T di G , allora G è un albero ed è identico a T (cioè un albero ha un albero ricoprente unico ed è esso stesso).

Applicazioni

Diversi algoritmi di pathfinding , incluso l'algoritmo di Dijkstra e l' algoritmo di ricerca A* , costruiscono internamente uno spanning tree come passaggio intermedio nella risoluzione del problema.

Al fine di ridurre al minimo il costo delle reti elettriche, dei collegamenti elettrici, delle tubazioni, del riconoscimento vocale automatico, ecc., le persone spesso utilizzano algoritmi che costruiscono gradualmente uno spanning tree (o molti di questi alberi) come passaggi intermedi nel processo di ricerca dello spanning tree minimo .

Internet e molte altre reti di telecomunicazioni hanno collegamenti di trasmissione che collegano i nodi in una topologia mesh che include alcuni loop. Al fine di evitare loop di bridge e loop di routing , molti protocolli di routing progettati per tali reti, tra cui Spanning Tree Protocol , Open Shortest Path First , Link-state routing protocol , Augmented tree-based routing , ecc., richiedono che ogni router ricordi un albero di copertura.

Un tipo speciale di albero ricoprente , l' albero di Xuong , viene utilizzato nella teoria dei grafi topologici per trovare le inclusioni di grafi con genere massimo . Un albero Xuong è un albero ricoprente tale che, nel grafo rimanente, il numero di componenti connessi con un numero dispari di archi sia il più piccolo possibile. Un albero Xuong e un'incorporamento di genere massimo associato possono essere trovati in tempo polinomiale .

Definizioni

Un albero è un grafo connesso non orientato senza cicli . È un albero di copertura di un grafo G se si estende su G (cioè include ogni vertice di G ) ed è un sottografo di G (ogni arco nell'albero appartiene a G ). Uno spanning tree di un grafo connesso G può anche essere definito come un insieme massimo di archi di G che non contiene cicli, o come un insieme minimo di archi che connettono tutti i vertici.

Cicli fondamentali

L'aggiunta di un solo bordo a un albero ricoprente creerà un ciclo; tale ciclo è chiamato ciclo fondamentale . C'è un ciclo fondamentale distinto per ogni arco non nello spanning tree; quindi, c'è una corrispondenza biunivoca tra cicli fondamentali e archi non nello spanning tree. Per un grafo connesso con V vertici, qualsiasi albero ricoprente avrà V  - 1 archi, e quindi, un grafo di E archi e uno dei suoi alberi ricoprenti avrà E  -  V  + 1 cicli fondamentali (Il numero di archi sottratto per il numero di bordi inclusi in uno spanning tree; indicando il numero di bordi non inclusi nello spanning tree). Per ogni dato albero ricoprente l'insieme di tutti  i cicli fondamentali E  −  V +1 forma una base ciclica , una base per lo spazio dei cicli .

Cutset fondamentali

Duplice alla nozione di ciclo fondamentale è la nozione di cutset fondamentale . Eliminando solo un bordo dello spanning tree, i vertici vengono partizionati in due insiemi disgiunti. Il cutset fondamentale è definito come l'insieme degli archi che devono essere rimossi dal grafo G per realizzare la stessa partizione. Quindi, ogni spanning tree definisce un insieme di V  − 1 cutset fondamentali, uno per ogni bordo dello spanning tree.

La dualità tra cutset fondamentali e cicli fondamentali viene stabilita osservando che gli archi del ciclo non nell'albero di copertura possono apparire solo negli insiemi degli altri archi del ciclo; e viceversa : i bordi in un insieme di taglio possono apparire solo in quei cicli che contengono il bordo corrispondente al gruppo di taglio. Questa dualità può essere espressa anche utilizzando la teoria dei matroidi , secondo la quale un albero ricoprente è una base del matroide grafico , un ciclo fondamentale è l'unico circuito all'interno dell'insieme formato aggiungendo un elemento alla base, e vengono definiti i cutset fondamentali allo stesso modo dal doppio matroide .

Attraversando foreste

Nei grafici che non sono collegati, non ci può essere spanning tree e si deve considerare invece lo spanning forest . Qui ci sono due definizioni concorrenti:

• Alcuni autori considerano una foresta di copertura come un sottografo aciclico massimale del grafo dato, o equivalentemente un grafo costituito da un albero di copertura in ogni componente connesso del grafo.
• Per altri autori, una foresta estesa è una foresta che si estende su tutti i vertici, il che significa solo che ogni vertice del grafo è un vertice nella foresta. Per questa definizione, anche un grafo connesso può avere una foresta di copertura disconnessa, come la foresta in cui ogni vertice forma un albero a vertice singolo.

Per evitare confusione tra queste due definizioni, Gross & Yellen (2005) suggeriscono il termine "full spanning forest" per una spanning forest con la stessa connettività del grafo dato, mentre Bondy & Murty (2008) chiamano invece questo tipo di foresta un " foresta di massima estensione”.

Contare gli alberi di copertura

La formula di Cayley conta il numero di alberi di copertura su un grafico completo. Ci sono alberi in , alberi in e alberi in .${\displaystyle 2^{2-2}=1}$${\displaystyle K_{2}}$${\displaystyle 3^{3-2}=3}$${\displaystyle K_{3}}$${\displaystyle 4^{4-2}=16}$${\displaystyle K_{4}}$

Il numero t ( G ) degli alberi di copertura di un grafo connesso è un invariante ben studiato .

In grafici specifici

In alcuni casi, è facile calcolare direttamente t ( G ):

• Se G è esso stesso un albero, allora t ( G ) = 1 .
• Quando G è il grafo del ciclo C _n con n vertici, allora t ( G ) =  n .
• Per un grafo completo con n vertici, la formula di Cayley fornisce il numero di alberi di copertura come n ^{n  − 2} .
• Se G è il grafo bipartito completo , allora .${\displaystyle K_{p,q}}$${\displaystyle t(G)=p^{q-1}q^{p-1}}$
• Per il grafo ipercubo n- dimensionale , il numero di alberi di copertura è . ${\displaystyle Q_{n}}$${\displaystyle t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$

In grafici arbitrari

Più in generale, per qualsiasi grafo G , il numero t ( G ) può essere calcolato in tempo polinomiale come determinante di una matrice derivata dal grafo, utilizzando il teorema matrice-albero di Kirchhoff .

Nello specifico, per calcolare t ( G ), si costruisce la matrice laplaciana del grafo, una matrice quadrata in cui le righe e le colonne sono entrambe indicizzate dai vertici di G . La voce nella riga i e nella colonna j è uno dei tre valori:

• Il grado del vertice i , se i  =  j ,
• −1, se i vertici i e j sono adiacenti, o
• 0, se i vertici i e j sono diversi tra loro ma non adiacenti.

La matrice risultante è singolare , quindi il suo determinante è zero. Tuttavia, l'eliminazione della riga e della colonna per un vertice scelto arbitrariamente porta a una matrice più piccola il cui determinante è esattamente  t ( G ).

Cancellazione-contrazione

Se G è un grafo o un multigrafo ed e è un arco arbitrario di G , allora il numero t ( G ) di alberi di copertura di G soddisfa la ricorrenza di delezione-contrazione t ( G ) =  t ( G  −  e ) +  t ( G / e ), dove G  −  e è il multigrafo ottenuto eliminando e e G / e è la contrazione di G per e . Il termine t ( G  -  e ) in questa formula conta gli alberi di copertura di  G che non usano l' arco  e , e il termine t ( G / e ) conta gli alberi di copertura di  G che usano  e .

In questa formula, se il grafo dato G è un multigrafo , o se una contrazione fa sì che due vertici siano collegati tra loro da più archi, allora gli archi ridondanti non dovrebbero essere rimossi, poiché ciò porterebbe al totale sbagliato. Ad esempio, un grafo di legame che collega due vertici mediante k archi ha k diversi alberi di copertura, ciascuno costituito da uno solo di questi archi.

Tutte polinomio

Il polinomio di Tutte di un grafo può essere definito come una somma, sugli alberi di copertura del grafo, di termini calcolati dall'"attività interna" e dall'"attività esterna" dell'albero. Il suo valore agli argomenti (1,1) è il numero di alberi di copertura o, in un grafo disconnesso, il numero di foreste di copertura massima.

Il polinomio di Tutte può anche essere calcolato utilizzando una ricorrenza di delezione-contrazione, ma la sua complessità computazionale è elevata: per molti valori dei suoi argomenti, calcolarlo esattamente è #P-completo , ed è anche difficile da approssimare con un rapporto di approssimazione garantito . Il punto (1,1), in cui può essere valutato usando il teorema di Kirchhoff, è una delle poche eccezioni.

Algoritmi

Costruzione

Un singolo albero ricoprente di un grafo può essere trovato in tempo lineare tramite la ricerca in profondità o in ampiezza . Entrambi questi algoritmi esplorano il grafo dato, partendo da un vertice arbitrario v , eseguendo un ciclo attraverso i vicini dei vertici che scoprono e aggiungendo ciascun vicino inesplorato a una struttura dati da esplorare in seguito. Differiscono se questa struttura dati è uno stack (nel caso della ricerca in profondità) o una coda (nel caso della ricerca in ampiezza). In entrambi i casi, si può formare uno spanning tree collegando ogni vertice, diverso dal vertice radice v , al vertice da cui è stato scoperto. Questo albero è noto come albero di ricerca in profondità o albero di ricerca in ampiezza in base all'algoritmo di esplorazione del grafo utilizzato per costruirlo. Gli alberi di ricerca in profondità sono un caso speciale di una classe di alberi di copertura chiamati alberi di Trémaux , dal nome dello scopritore del XIX secolo della ricerca in profondità.

Gli spanning tree sono importanti nell'elaborazione parallela e distribuita, come mezzo per mantenere le comunicazioni tra un insieme di processori; si veda ad esempio lo Spanning Tree Protocol utilizzato dai dispositivi a livello di collegamento OSI o lo Shout (protocollo) per il calcolo distribuito. Tuttavia, i metodi depth-first e breadth-first per costruire spanning tree su computer sequenziali non sono adatti per computer paralleli e distribuiti. Invece, i ricercatori hanno ideato diversi algoritmi più specializzati per trovare spanning tree in questi modelli di calcolo.

Ottimizzazione

In certi campi della teoria dei grafi è spesso utile trovare uno spanning tree minimo di un grafo pesato . Sono stati studiati anche altri problemi di ottimizzazione sugli spanning tree, tra cui lo spanning tree massimo, l'albero minimo che si estende su almeno k vertici, lo spanning tree con il minor numero di spigoli per vertice , lo spanning tree con il maggior numero di foglie , lo spanning tree con il minor numero di foglie (strettamente correlato al problema del cammino hamiltoniano ), l'albero ricoprente di diametro minimo e l'albero ricoprente di minima dilatazione.

Sono stati studiati anche problemi di spanning tree ottimali per insiemi finiti di punti in uno spazio geometrico come il piano euclideo . Per tale input, uno spanning tree è ancora un albero che ha come vertici i punti dati. La qualità dell'albero viene misurata allo stesso modo di un grafico, utilizzando la distanza euclidea tra coppie di punti come peso per ciascun bordo. Così, per esempio, un albero di copertura minimo euclideo è lo stesso di un albero di copertura minimo di un grafo in un grafo completo con pesi degli archi euclidei. Tuttavia, non è necessario costruire questo grafico per risolvere il problema di ottimizzazione; il problema dell'albero di copertura del minimo euclideo, ad esempio, può essere risolto in modo più efficiente in tempo O ( n  log  n ) costruendo la triangolazione di Delaunay e quindi applicando un algoritmo di albero di copertura del minimo del grafico planare temporale lineare alla triangolazione risultante.

Randomizzazione

Un albero ricoprente scelto casualmente tra tutti gli alberi ricoprenti con uguale probabilità è detto albero ricoprente uniforme . L'algoritmo di Wilson può essere utilizzato per generare alberi di copertura uniformi in tempo polinomiale mediante un processo che consiste nel fare una passeggiata casuale sul grafico dato e cancellare i cicli creati da questa passeggiata.

Un modello alternativo per generare spanning tree in modo casuale ma non uniforme è lo spanning tree casuale minimo . In questo modello, ai bordi del grafico vengono assegnati pesi casuali e quindi viene costruito l' albero di copertura minimo del grafico ponderato.

Enumerazione

Poiché un grafo può avere molti alberi di copertura in modo esponenziale, non è possibile elencarli tutti in tempo polinomiale . Tuttavia, sono noti algoritmi per elencare tutti gli spanning tree in tempo polinomiale per albero.

In grafici infiniti

Ogni grafo connesso finito ha uno spanning tree. Tuttavia, per grafi connessi infiniti, l'esistenza di alberi di copertura è equivalente all'assioma di scelta . Un grafo infinito è connesso se ogni coppia dei suoi vertici forma la coppia di punti finali di un cammino finito. Come con i grafi finiti, un albero è un grafo connesso senza cicli finiti e uno spanning tree può essere definito come un insieme aciclico massimo di archi o come un albero che contiene ogni vertice.

Gli alberi all'interno di un grafo possono essere parzialmente ordinati dalla loro relazione sottografo, e qualsiasi catena infinita in questo ordine parziale ha un limite superiore (l'unione degli alberi nella catena). Il lemma di Zorn , una delle tante affermazioni equivalenti all'assioma della scelta, richiede che un ordine parziale in cui tutte le catene sono limitate in alto abbia un elemento massimale; nell'ordine parziale sugli alberi del grafo, questo elemento massimale deve essere uno spanning tree. Pertanto, se si assume il lemma di Zorn, ogni grafo connesso infinito ha uno spanning tree.

Viceversa, data una famiglia di insiemi , è possibile costruire un grafo infinito tale che ad ogni albero ricoprente del grafo corrisponda una funzione di scelta della famiglia di insiemi. Pertanto, se ogni grafo connesso infinito ha uno spanning tree, allora l'assioma della scelta è vero.

In multigrafi diretti

L'idea di un albero ricoprente può essere generalizzata ai multigrafi diretti. Dato un vertice v su un multigrafo orientato G , uno spanning tree orientato T radicato in v è un sottografo aciclico di G in cui ogni vertice diverso da v ha grado esterno 1. Questa definizione è soddisfatta solo quando i "rami" di T puntano verso v .

Guarda anche

• Algoritmo di allagamento
• Buon albero ricoprente – Albero ricoprente per grafi planari incorporati

Riferimenti