Scala (grafo)
Nell'ambito matematico della teoria dei grafi, un grafo a scala, denotato con , è un grafo planare non orientato avente 2n vertici e 3n-2 spigoli.[1]
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: .[2][3]
Proprietà
modificaPer costruzione, il grafo a scala è isomorfo al grafo a griglia e appare con la forma di una scala di n gradini. È un cammino hamiltoniano avente:
- calibro pari a 4, se (caso del grafo a scala non degenere);
- indice cromatico uguale a 3, se .
Il numero cromatico del grafo a scala è 2, mentre il polinomio cromatico è .
-
Il numero cromatico del grafo a scala è 2
Ladder rung graph
modificaTalora, l'espressione "grafo a scala" indica il grafo a scala di livello (ladder rung graph, LR) denotato con , poiché è l'unione grafica di n copie del grafo lineare P2:
Grafo a scala circolare
modificaIl grafo a scala circolare (in inglese: Circular ladder graph) CLn 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: CLn = Kn × Cn)[4], ovvero di un grafo ciclo di lunghezza n≥3 con uno lineare (in simboli: CLn = Cn × P2).[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.
CL3 |
CL4 |
CL5 |
CL6 |
CL7 |
CL8 |
Scala di Möbius
modificaSe 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:
Note
modifica- ^ Ladder Graph, su MathWorld.
- ^ Haruo Hosoya e Frank Harary, On the Matching Properties of Three Fence Graphs, in J. Math. Chem., vol. 12, n. 1, 1993, pp. 211-218, DOI:10.1007/BF01164636, OCLC 5655263804.
- ^ Mark Noy e Ares Ribó, Recursively Constructible Families of Graphs, in Advances in Applied Mathematics, 2004, DOI:10.1016/S0196-8858(03)00088-5, ISSN 0196-8858 , OCLC 4927830318. URL consultato il 31 gennaio 2020 (archiviato dall'url originale il 31 gennaio 2020).
- ^ Yichao Chen, Jonathan L. Gross e Toufik Mansour, Total Embedding Distributions of Circular Ladders, in Journal of Graph Theory, vol. 74, n. 1, settembre 2013, pp. 32–57, DOI:10.1002/jgt.21690.
Altri progetti
modifica- Wikimedia Commons contiene immagini o altri file su Scala (grafo)
Collegamenti esterni
modifica- (EN) Eric W. Weisstein, Scala (grafo), su MathWorld, Wolfram Research.