Grafico ipercubo - Hypercube graph

Grafico ipercubo
Il grafico ipercubo Q 4
vertici	2 n
bordi	2 n -1 n
Diametro	n
Circonferenza	4 se n ≥ 2
automorfismi	n ! 2 n
Numero cromatico	2
Spettro	${\displaystyle \{(n-2k)^{\binom {n}{k}};k=0,\ldots ,n\}}$
Proprietà	Simmetrica Distanza regolare Unità di distanza Hamiltoniana Bipartita
Notazione	Q n
Tabella di grafici e parametri

Nella teoria dei grafi , il grafo ipercubo Q _n è il grafo formato dai vertici e dai bordi di un ipercubo n- dimensionale . Ad esempio, il grafo cubico Q ₃ è il grafo formato dagli 8 vertici e dai 12 spigoli di un cubo tridimensionale. Q _n ha 2 ⁿ vertici , 2 ^{n −1} n archi ed è un grafo regolare con n archi che toccano ciascun vertice.

Il grafo ipercubo Q _n può anche essere costruito creando un vertice per ogni sottoinsieme di un insieme di n elementi, con due vertici adiacenti quando i loro sottoinsiemi differiscono in un singolo elemento, o creando un vertice per ogni numero binario di n cifre , con due vertici adiacenti quando le loro rappresentazioni binarie differiscono in una singola cifra. È il prodotto cartesiano n- fold del grafo completo di due vertici e può essere scomposto in due copie di Q _{n − 1} collegate tra loro da un matching perfetto .

I grafici ipercubo non devono essere confusi con i grafici cubici , che sono grafici che hanno esattamente tre bordi che toccano ciascun vertice. L'unico grafo ipercubo Q _n che è un grafo cubico è il grafo cubico Q ₃ .

Costruzione

Costruzione di Q ₃ collegando coppie di vertici corrispondenti in due copie di Q ₂

Il grafo ipercubo Q _n può essere costruito dalla famiglia dei sottoinsiemi di un insieme con n elementi, creando un vertice per ogni possibile sottoinsieme e unendo due vertici con un arco ogni volta che i corrispondenti sottoinsiemi differiscono in un singolo elemento. In modo equivalente, può essere costruito utilizzando 2 ⁿ vertici etichettati con numeri binari a n bit e collegando due vertici tramite un bordo ogni volta che la distanza di Hamming delle loro etichette è uno. Queste due costruzioni sono strettamente correlati: un numero binario può essere interpretata come un insieme (l'insieme di posizioni in cui ha un 1 cifra), e due tali insiemi differire in un unico elemento ogniqualvolta le corrispondenti due numeri binari hanno una distanza di Hamming.

In alternativa, Q _n può essere costruito dall'unione disgiunta di due ipercubi Q _{n − 1} , aggiungendo un arco da ciascun vertice in una copia di Q _{n − 1} al vertice corrispondente nell'altra copia, come mostrato in figura. I bordi di giunzione formano un abbinamento perfetto .

Un'altra costruzione di Q _n è il prodotto cartesiano di n grafi completi di due vertici K ₂ . Più in generale il prodotto cartesiano di copie di un grafo completo è chiamato grafo di Hamming ; i grafici dell'ipercubo sono esempi di grafici di Hamming.

Esempi

Il grafo Q _{0 è} costituito da un solo vertice, mentre Q ₁ è il grafo completo su due vertici e Q ₂ è un ciclo di lunghezza  4 .

Il grafo Q ₃ è l' 1-scheletro di un cubo , un grafo cubico , un grafo planare con otto vertici e dodici spigoli .

Il grafo Q ₄ è il grafo di Levi della configurazione di Möbius . È anche il grafico del cavaliere per una scacchiera toroidale . ${\displaystyle 4\times 4}$

Proprietà

Bipartitismo

Ogni grafo ipercubo è bipartito : può essere colorato con solo due colori. I due colori di questa colorazione possono essere trovati dalla costruzione di sottoinsiemi di grafici ipercubo, dando un colore ai sottoinsiemi che hanno un numero pari di elementi e l'altro colore ai sottoinsiemi con un numero dispari di elementi.

Hamiltonicità

Un ciclo Hamiltoniano su un tesseract con vertici etichettati con un codice Gray ciclico a 4 bit

Ogni ipercubo Q _n con n  > 1 ha un ciclo hamiltoniano , un ciclo che visita ogni vertice esattamente una volta. Inoltre, esiste un cammino hamiltoniano tra due vertici u e v se e solo se hanno colori diversi in una colorazione 2 del grafo. Entrambi i fatti sono facili da dimostrare utilizzando il principio di induzione sulla dimensione dell'ipercubo e la costruzione del grafico dell'ipercubo unendo due ipercubi più piccoli con un matching.

L' Hamiltonicità dell'ipercubo è strettamente correlata alla teoria dei codici Gray . Più precisamente esiste una corrispondenza biunivoca tra l'insieme dei codici Gray ciclici a n bit e l'insieme dei cicli Hamiltoniani nell'ipercubo Q _n . Una proprietà analoga vale per codici Gray aciclici a n- bit e cammini hamiltoniani.

Un fatto meno noto è che ogni corrispondenza perfetta nell'ipercubo si estende a un ciclo hamiltoniano. La questione se ogni matching si estenda a un ciclo hamiltoniano rimane un problema aperto.

Altre proprietà

Il grafo ipercubo Q _n (per n > 1 ) :

• è il diagramma di Hasse di un'algebra booleana finita .
• è un grafico mediano . Ogni grafico mediano è un sottografo isometrico di un ipercubo e può essere formato come retrazione di un ipercubo.
• ha più di 2 ^{2 n-2} abbinamenti perfetti. (questa è un'altra conseguenza che segue facilmente dalla costruzione induttiva.)
• è un arco transitivo e simmetrico . Le simmetrie dei grafi ipercubo possono essere rappresentate come permutazioni con segno .
• contiene tutti i cicli di lunghezza 4, 6, ..., 2 ⁿ ed è quindi un grafo bipanciclico .
• può essere disegnato come un grafo della distanza unitaria nel piano euclideo utilizzando la costruzione del grafo ipercubo da sottoinsiemi di un insieme di n elementi, scegliendo un vettore unitario distinto per ciascun elemento dell'insieme e ponendo il vertice corrispondente all'insieme S al somma dei vettori in S .
• è un grafo connesso a n vertici , per il teorema di Balinski
• è planare (può essere disegnato senza incroci) se e solo se n ≤ 3 . Per valori maggiori di n , l'ipercubo ha genere ( n − 4) 2 ^{n − 3} + 1 .
• ha esattamente alberi di copertura .${\displaystyle 2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \scegli k}}$
• ha esattamente larghezza di banda .${\displaystyle \sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}}$
• ha numero acromatico proporzionale a , ma la costante di proporzionalità non è nota con precisione.${\displaystyle {\sqrt {n2^{n}}}}$
• ha come autovalori della sua matrice di adiacenza i numeri (− n , − n + 2, − n + 4, ... , n − 4, n − 2, n ) e come autovalori della sua matrice laplaciana i numeri (0 , 2, ..., 2n ) . L' autovalore k ha molteplicità in entrambi i casi.${\displaystyle {\binom {n}{k}}}$
• ha numero isoperimetrico h ( G ) = 1 .

La famiglia Q _n per ogni n > 1 è una famiglia di grafi di Lévy

I problemi

Lunghezze massime dei serpenti ( L _s ) e delle spire ( L _c ) nel problema degli snakes-in-the-box per le dimensioni n da 1 a 4

Il problema di trovare il percorso o il ciclo più lungo che sia un sottografo indotto di un dato grafico ipercubo è noto come problema del serpente nella scatola .

La congettura di Szymanski riguarda l'idoneità di un ipercubo come topologia di rete per le comunicazioni. Afferma che, indipendentemente da come si sceglie una permutazione che collega ciascun vertice dell'ipercubo a un altro vertice con cui dovrebbe essere connesso, c'è sempre un modo per connettere queste coppie di vertici tramite percorsi che non condividono alcun bordo diretto.

Guarda anche

• grafico di de Bruijn
• Cicli collegati al cubo
• Cubo di Fibonacci
• Grafico del cubo piegato
• Grafico Frankl-Rödl
• Grafico del cubo dimezzato
• Topologia di rete Hypercube
• cubo parziale

Appunti

Riferimenti

• Harary, F. ; Hayes, JP; Wu, H.-J. (1988), "A survey of the theory of hypercube graphs", Computers & Mathematics with Applications , 15 (4): 277–289, doi : 10.1016/0898-1221(88)90213-1 , hdl : 2027.42/27522.