Potenza del grafico - Graph power

Il quadrato di un grafico

Nella teoria dei grafi , una branca della matematica, la k- esima potenza G ^k di un grafo non orientato G è un altro grafo che ha lo stesso insieme di vertici , ma in cui due vertici sono adiacenti quando la loro distanza in G è al massimo  k . Le potenze dei grafi sono indicate con una terminologia simile a quella dell'elevamento a potenza dei numeri: G ² è chiamato il quadrato di G , G ³ è chiamato il cubo di G , ecc.

Le potenze del grafo dovrebbero essere distinte dai prodotti di un grafo con se stesso, che (a differenza delle potenze) generalmente hanno molti più vertici rispetto al grafo originale.

Proprietà

Se un grafico ha diametro d , allora la sua potenza d -esima è il grafico completo . Se una famiglia di grafi ha una larghezza di cricca limitata , allora anche le sue potenze d -esime per ogni d fisso .

Colorazione

La colorazione del grafico sul quadrato di un grafico può essere utilizzata per assegnare le frequenze ai partecipanti delle reti di comunicazione wireless in modo che due partecipanti non interferiscano l'uno con l'altro in nessuno dei loro vicini comuni e per trovare disegni grafici con un'elevata risoluzione angolare .

Sia il numero cromatico che la degenerazione della k- esima potenza di un grafo planare di massimo grado sono , dove il limite di degenerazione mostra che un algoritmo di colorazione greedy può essere utilizzato per colorare il grafo con questi molti colori. Per il caso speciale di un quadrato di un grafo planare, Wegner nel 1977 ha ipotizzato che il numero cromatico del quadrato di un grafo planare sia al massimo , ed è noto che il numero cromatico sia al massimo . Più in generale, per qualsiasi grafo con degenerazione d e grado massimo Δ, la degenerazione del quadrato del grafo è O ( d Δ), quindi molti tipi di grafi sparsi diversi dai grafi planari hanno anche quadrati il ​​cui numero cromatico è proporzionale a . ${\displaystyle O(\Delta ^{\lfloor k/2\rfloor })}$${\displaystyle \max \left(\Delta +5,{\frac {3\Delta }{2}}+1\right)}$${\displaystyle {\frac {5\Delta }{3}}+O(1)}$

Sebbene il numero cromatico del quadrato di un grafo non planare con grado massimo possa essere proporzionale a ² nel caso peggiore, è più piccolo per grafi di grande circonferenza , essendo limitato da O(Δ ² /log Δ) in questo caso.

Determinare il numero minimo di colori necessari per colorare il quadrato di un grafico è NP-difficile , anche nel caso planare.

Hamiltonicità

Il cubo di ogni grafo connesso contiene necessariamente un ciclo hamiltoniano . Non è necessariamente il caso che il quadrato di un grafo connesso sia hamiltoniano, ed è NP-completo determinare se il quadrato è hamiltoniano. Tuttavia, per il teorema di Fleischner , il quadrato di un grafo connesso a 2 vertici è sempre hamiltoniano.

Complessità computazionale

La k- esima potenza di un grafo con n vertici e m archi può essere calcolata in tempo O( mn ) eseguendo una prima ricerca in ampiezza a partire da ciascun vertice per determinare le distanze da tutti gli altri vertici, o leggermente più velocemente utilizzando algoritmi più sofisticati. In alternativa, se A è una matrice di adiacenza per il grafo, modificata per avere elementi diversi da zero sulla sua diagonale principale, allora gli elementi diversi da zero di A ^k danno la matrice di adiacenza della k- esima potenza del grafo, da cui segue che costruendo k- esima le potenze possono essere eseguite in un lasso di tempo che è all'interno di un fattore logaritmico del tempo per la moltiplicazione matriciale .

Le k- esime potenze degli alberi sono riconoscibili nel tempo lineare nella dimensione del grafo di input.

Dato un grafico, decidere se è il quadrato di un altro grafico è NP-completo . Inoltre, è NP-completo determinare se un grafo è una k- esima potenza di un altro grafo, per un dato numero k  ≥ 2, o se è una k- esima potenza di un grafo bipartito , per k  > 2.

sottografi indotti

K ₄ come il semiquadrato di un grafico cubo

Il semiquadrato di un grafo bipartito G è il sottografo di G ² indotto da un lato della bipartizione di G . I grafici mappa sono i mezzi quadrati dei grafici planari e i grafici a cubo dimezzato sono i mezzi quadrati dei grafici ipercubo .

I poteri fogliari sono i sottografi dei poteri degli alberi indotti dalle foglie dell'albero. Una potenza foglia k è una potenza foglia il cui esponente è k .

Riferimenti