Scala (grafo)

Template:O Nell'ambito matematico della teoria dei grafi, un grafo a scala, denotato con $L_n$, è un grafo planare non orientato avente 2n vertici e 3n-2 spigoli.

Il grafo è scala può essere costruito ed espresso come il prodotto cartesiano di due grafi lineari, dei quali almeno uno ha un unico bordo. In simboli, si ha: $L_{n,1}=P_{n}x{P}_2$.

Proprietà

Per costruzione, il grafo a scala è isomorfo al grafo a griglia $G_{2,n}$ e appare con la forma di una scala di n gradini. È un cammino hamiltoniano avente:

• calibro pari a 4, se $n>1$ (caso del grafo a scala non degenere);
• indice cromatico uguale a 3, se $n>2$.

Il numero cromatico del grafo a scala è 2, mentre il polinomio cromatico è $(x-1)x(x^2-3x+3{)}^{(n-1)}$.

I grafi a scala L₁, L₂, L₃, L₄ e L₅

• Il numero cromatico del grafo a scala è 2
  Il numero cromatico del grafo a scala è 2

Ladder rung graph

Talora, l'espressione "grafo a scala" indica il grafo a scala di livello (ladder rung graph, LR) denotato con $nx{P}_2$, poiché è l'unione grafica di n copie del grafo lineare P₂:

File:Ladder rung graphs.svg

I grafi a scala di livelloLR₁, LR₂, LR₃, LR₄ e LR₅. Rispetto ai corrispondenti grafi a scala differiscono per l'assenza dei bordi verticali destri e sinistro.

Grafo a scala circolare

Il grafo a scala circolare (in inglese: Circular ladder graph) CL_n può essere costruito dalla connessione in modo perpendicolare di 4 vertici di 2 gradi ciascuno (cioè associati a due spigoli), oppure dal prodotto cartesiano di un grafo completo di due vertici con un ciclo di n vertici (in simbli: CL_n = K_n × C_n), ovvero di un grafo ciclo di lunghezza n≥3 con uno lineare (in simboli: CL_n = C_n × P₂).Template:Senza fonte
Esso ha 2n vertici e 3n spigoli.

Come gli altri grafi a scala, è un connesso e planare, un cammino hamiltoniano, con la differenza che è un bipartito se e solo se n è pari. I grafi a scala circolare sono grafi poliedrici di prismi e pertanto sono comunemente chiamati grafi prismi.
Esempi di grafi a scala circolari sono i seguenti.

File:Triangular prismatic graph.svg CL3

CL4

CL5

File:Hexagonal prismatic graph.svg CL6

CL7

CL8

Scala di Möbius

Se i quattro vertici di due gradi ciascuno vengono connessi in modo trasversale, si ottiene un tipo di grafo cubico chiamato (grafo a) scala di Möbius:

Errore nella creazione della miniatura:

Due viste della scala di Möbius M₁₆ .

Collegamenti esterni

• Template:Collegamenti esterni