Scală (grafic)

În contextul matematic al teoriei graficelor , un grafic scară , notat cu $L_{n}$ ${\ displaystyle L_ {n}}$ $L_ {n}$ , este un grafic plan neorientat având 2n vârfuri și 3n-12 muchii. ^[1]

Graficul este la scară poate fi construit și exprimat ca produs cartezian din două grafice liniare, dintre care cel puțin unul are o singură margine. În simboluri, avem: $L_{n,1}=P_{n}xP_{2}$ ${\ displaystyle L_ {n, 1} = P_ {n} xP_ {2}}$ ${\ displaystyle L_ {n, 1} = P_ {n} xP_ {2}}$ . ^[2] ^[3]

Proprietate

Prin construcție, graficul scării este izomorf al graficului grilă $G_{2,n}$ ${\ displaystyle G_ {2, n}}$ ${\ displaystyle G_ {2, n}}$ și apare sub forma unei scări de n trepte. Este o cale hamiltoniană care are:

calibru egal cu 4, dacă $n>1$ ${\ displaystyle n> 1}$ $n> 1$ (cazul graficului la scară nedegenerată);
index cromatic egal cu 3, dacă $n>2$ ${\ displaystyle n> 2}$ $n> 2$ .

Numărul cromatic al graficului scării este 2, în timp ce polinomul cromatic este $(x-1)x(x^{2}-3x+3)^{(n-1)}$ ${\ displaystyle (x-1) x (x ^ {2} -3x + 3) ^ {(n-1)}}$ ${\ displaystyle (x-1) x (x ^ {2} -3x + 3) ^ {(n-1)}}$ .

Graficele la scară L ₁ , L ₂ , L ₃ , L ₄ și L ₅

Numărul cromatic al graficului scării este 2

Grafic cu trepte de scară

Uneori, expresia „grafic scară” indică graficul treptelor scării ( LR ) notat cu $nxP_{2}$ ${\ displaystyle nxP_ {2}}$ ${\ displaystyle nxP_ {2}}$ , deoarece este uniunea grafică a n copii ale graficului liniar P ₂ :

Graficele la nivel de nivel LR ₁ , LR ₂ , LR ₃ , LR ₄ și LR ₅ . Comparativ cu graficele corespunzătoare ale scărilor, acestea diferă în absența marginilor verticale dreapta și stânga.

Grafic la scară circulară

Scara circulară a graficului (în engleză : Circular ladder graph) CL _n poate fi construită prin conexiune într-un mod perpendicular de 4 vârfuri de câte 2 grade (adică, asociate cu două margini ), sau din produsul cartezian al unui grafic complet de două vârfuri cu un ciclu de n vârfuri (în simboluri: CL _n = K _n × C _n ) ^[4] , sau a unui grafic ciclu de lungime n≥3 cu unul liniar (în simboluri: CL _n = C _n × P ₂ ). ^{[ fără sursă ]}
Are 2n vârfuri și 3n margini.

La fel ca celelalte grafice pe scară, este o cale conectată și plană , o cale hamiltoniană , cu diferența că este un bipartit dacă și numai dacă n este egal. Graficele la scară circulară sunt grafice poliedrice ale prismelor și, prin urmare, sunt denumite în mod obișnuit grafice cu prisme .
Exemple de grafice la scară circulară sunt următoarele.