Hispanopedia Wiki
Articulo de referencia

Cubicidad

Un gráfico con cubicidad 2 , realizado como el gráfico de intersección de cubos unitarios 2 paralelos a los ejes , es decir, cuadrados unitarios paralelos a los ejes, en el plan...

Hispanopedia WikiContenido en espanolLectura gratuita
Un gráfico con cubicidad 2 , realizado como el gráfico de intersección de cubos unitarios 2 paralelos a los ejes , es decir, cuadrados unitarios paralelos a los ejes, en el plano.

En el campo matemático de la teoría de grafos , la cubicidad es un invariante de grafos definido como la dimensión más pequeña tal que un grafo puede representarse como el grafo de intersección de cubos unitarios paralelos a los ejes en el espacio euclidiano . [ 1 ] La cubicidad fue introducida por Fred S. Roberts en 1969, junto con un invariante relacionado llamado boxicidad que considera la dimensión más pequeña necesaria para representar un grafo como el grafo de intersección de rectángulos paralelos a los ejes en el espacio euclidiano. [ 2 ]

Un gráfico de indiferencia con cubicidad 1 , realizado como el gráfico de intersección de cubos unitarios 1 , es decir intervalos unitarios, en la recta numérica real .

Definición

Este artículo solo considera grafos simples, no dirigidos , con conjuntos de vértices finitos y no vacíos. [ 3 ] [ 4 ]

La cubicidad de un gráficoGRAMO{\displaystyle G}, denotado porcachorro⁡(GRAMO){\displaystyle \operatorname {cub} (G)}es el entero más pequeñok{\displaystyle k}de tal manera queGRAMO{\displaystyle G}puede representarse como la gráfica de intersección de unidades cerradas paralelas a los ejesk{\displaystyle k}-cubos enk{\displaystyle k}espacio euclidiano de -dimensiones,mik{\displaystyle \mathrm {E} ^{k}}. [ 5 ] [ 6 ] [ 7 ]

Parak≥1{\displaystyle k\geq 1}, un gráficoGRAMO{\displaystyle G}puede tener tal representación enmik{\displaystyle \mathrm {E} ^{k}}si y solo siGRAMO{\displaystyle G}es la intersección dek{\displaystyle k}gráficos de indiferencia en el mismo conjunto de vértices queGRAMO{\displaystyle G}. [ 8 ]

La cubicidad de un grafo completo se define como cero. [ 9 ]

Relaciones con ciertas clases de grafos, límite superior

Para un gráficoGRAMO, cachorro⁡(GRAMO)=0 {\displaystyle G,~\operatorname {cub} (G)=0~}si y solo siGRAMO{\displaystyle G}está completo. [ 10 ]

Para un gráficoGRAMO, cachorro⁡(GRAMO)=1 {\displaystyle G,~\operatorname {cub} (G)=1~}si y solo siGRAMO{\displaystyle G}es un gráfico de intervalo unitario que no está completo. [ 11 ]

Paranorte∈norte∗, cachorro⁡(K1,norte)=⌊registro2⁡(2norte−1)⌋, {\displaystyle n\in \mathbb {N} ^{*}\!,~\operatorname {cub} (K_{1,n})=\lfloor \log _{2}(2n-1)\rfloor ,~}dóndeK1,norte{\displaystyle K_{1,n}}denota el gráfico estrella de (1{\displaystyle 1}centro y)norte{\displaystyle n}vértices y⌊⋅⌋{\displaystyle \lfloor \cdot \rfloor }denota la función piso . [ 12 ] [ 13 ]

Parapag∈norte∗, cachorro⁡(Kpag(2))=pag, {\displaystyle p\in \mathbb {N} ^{*}\!,~\operatorname {cub} (K_{p(2)})=p,~}dóndeKpag(2){\displaystyle K_{p(2)}}denota el grafo multipartito completo conpag{\displaystyle p}partes de cardinal2{\displaystyle 2}. [ 14 ] [ 15 ]

Para un gráficoGRAMO{\displaystyle G}ennorte{\displaystyle n}vértices, cachorro⁡(GRAMO)≤⌊2norte/3⌋. {\displaystyle ~\operatorname {cub} (G)\leq \lfloor 2n/3\rfloor .~}Además, este límite superior es el mejor posible en términos denorte{\displaystyle n}. [ 16 ] [ 17 ]

Relaciones con otras dimensiones del gráfico

Relaciones con la boxicidad: límites

La cubicidad de un gráficoGRAMO{\displaystyle G}está estrechamente relacionado con su boxicidad, denotada porcaja⁡(GRAMO).{\displaystyle \operatorname {box} (G).}La definición de boxicidad es esencialmente la misma que la de cubicidad, pero con cajas paralelas a los ejes en lugar de cubos unitarios paralelos a los ejes.

Dado que un cubo es un caso especial de una caja, la cubicidad de un gráficoGRAMO{\displaystyle G}es siempre un límite superior para su boxicidad, es decir, caja⁡(GRAMO)≤cachorro⁡(GRAMO).{\displaystyle ~\operatorname {box} (G)\leq \operatorname {cub} (G).}

En la otra dirección, se puede demostrar que para un gráficoGRAMO{\displaystyle G}ennorte{\displaystyle n}vértices, cachorro⁡(GRAMO)≤⌈registro2⁡norte⌉caja⁡(GRAMO), {\displaystyle ~\operatorname {cub} (G)\leq \lceil \log _{2}n\rceil \operatorname {box} (G),~}dónde⌈⋅⌉{\displaystyle \lceil \cdot \rceil }denota la función techo . Además, este límite superior es ajustado. [ 18 ]

Relaciones con la esfericidad

La esfericidad de un gráficoGRAMO,{\displaystyle G,}denotado porsph⁡(GRAMO),{\displaystyle \operatorname {sph} (G),}se define de la misma manera que la cubicidad, pero con esferas congruentes en lugar de cubos unitarios paralelos a los ejes.

Para ciertos gráficos, la cubicidad supera a la esfericidad; la estrella de cinco puntas,K1,5,{\displaystyle K_{1,5},}es un ejemplo: cachorro⁡(K1,5)=3>sph⁡(K1,5)=2.{\displaystyle ~\operatorname {cub} (K_{1,5})=3>\operatorname {sph} (K_{1,5})=2.}[ 19 ]

En la otra dirección, gráficosGRAMO{\displaystyle G}puede construirse de manera que sph⁡(GRAMO)>cachorro⁡(GRAMO)=k, {\displaystyle ~\operatorname {sph} (G)>\operatorname {cub} (G)=k,~}parak∈{2,3}.{\displaystyle k\in \{2,3\}.}[ 20 ]

Notas

  1. ↑ Fishburn (1983 , pág. 309, Sección 1) 
  2. ↑ Roberts (1969 , págs. 301–310) 
  3. ↑ Chandran y Mathew (2009 , pág. 2, Sección 1) 
  4. ↑ Fishburn (1983 , pág. 309, Sección 1) 
  5. ↑ Roberts (1969 , p. 302, Sección 1) utiliza cubos cerrados de longitud de lado 1{\displaystyle 1}. Nota al pie 1 en la pág. 302: "Las cajas no están necesariamente cerradas, aunque no es difícil demostrar que si una representación [deGRAMO{\displaystyle G}] es alcanzable con [abierto] cuadros enmik{\displaystyle \mathrm {E} ^{k}}, es alcanzable con cajas cerradas enmik{\displaystyle \mathrm {E} ^{k}}.".
  6. ↑ Chandran y Mathew (2009 , p. 2, Sección 1, Definición 4) utilizan productos cartesianos de intervalos cerrados. [ai,ai+1]{\displaystyle [a_{i},a_{i}+1]}.
  7. ↑ Fishburn (1983 , pág. 309, Sección 1) 
  8. ↑ Roberts (1969 , págs. 302–303, Sección 2) En efecto: ∀ tú,v∈V(GRAMO),{\displaystyle \forall ~u,v\in \mathrm {V} (G),}{tú,v}∈mi(GRAMO){\displaystyle \{u,v\}\in \mathrm {E} (G)}si y solo si‖F(tú)−F(v)‖∞≤1,{\displaystyle \|f(u)-f(v)\|_{\infty }\leq 1,}si y solo si ∀ 1≤i≤k, |Fi(tú)−Fi(v)|≤1, {\displaystyle ~\forall ~1\leq i\leq k,~|f_{i}(u)-f_{i}(v)|\leq 1,~}es decir, {tú,v}∈mi(GRAMOi).{\displaystyle ~\{u,v\}\in \mathrm {E} (G_{i}).}Y entonces:∀ tú,w∈V(GRAMO),{\displaystyle \forall ~u,w\in \mathrm {V} (G),}{tú,w}∉mi(GRAMO){\displaystyle \{u,w\}\notin \mathrm {E} (G)}si y solo si‖F(tú)−F(w)‖∞>1,{\displaystyle \|f(u)-f(w)\|_{\infty }>1,}si y solo si ∃ 1≤i≤k {\displaystyle ~\exists ~1\leq i\leq k~}de tal manera que |Fi(tú)−Fi(w)|>1, {\displaystyle ~|f_{i}(u)-f_{i}(w)|>1,~}es decir, {tú,w}∉mi(GRAMOi);{\displaystyle ~\{u,w\}\notin \mathrm {E} (G_{i});}pero ∀ 1≤j≠i≤k, |Fj(tú)−Fj(w)|{\displaystyle ~\forall ~1\leq j\neq i\leq k,~|f_{j}(u)-f_{j}(w)|}tal vez≤1, {\displaystyle \leq 1,~}es decir, {tú,w}{\displaystyle ~\{u,w\}}puede∈mi(GRAMOj).{\displaystyle \in \mathrm {E} (G_{j}).}
  9. ↑ Chandran y Mathew (2009 , pág. 2, Sección 1, Definición 4) 
  10. ↑ Roberts (1969 , pág. 304, Sección 3, Demostración del Teorema 2) 
  11. ↑ Fishburn (1983 , pág. 310, Sección 1) 
  12. ↑ Roberts (1969 , pág. 303, Sección 3, Teorema 1) 
  13. ↑ Es decir, cub(K 1,n ) = ⌈log₂(n)⌉. Demostración: ∀ n ∈ ℕ*, 1 ≤ n; por lo tanto, 0 < n ≤ 2n−1. ∀ n ∈ ℕ*, ∃! c ∈ ℕ tal que n ≤ 2ᶜ ≤ 2n−1 (es decir, c es el menor k ∈ ℕ tal que n ≤ 2ᵏ); por lo tanto, ∃! c ∈ ℕ tal que log₂(n) ≤ c ≤ log₂(2n−1). Entonces, ⌈log₂(n)⌉ = c = ⌊log₂(2n−1)⌋.
  14. ↑ Fishburn (1983 , pág. 310, Sección 1) 
  15. ↑ Roberts (1969 , pág. 304, Sección 3, Teorema 2) 
  16. ↑ Fishburn (1983 , pág. 310, Sección 1) 
  17. ↑ Roberts (1969 , pág. 306, Sección 4, Teorema 5) 
  18. ↑ Chandran y Mathew (2009 , pág. 3, Sección 2, Teorema 1) 
  19. ↑ Fishburn (1983 , pág. 309, Sección 1) 
  20. ↑ Fishburn (1983 , págs. 310–318, secciones 2–3) 

Referencias

  • Chandran, L. Sunil; Mathew, K. Ashik (28 de abril de 2009), "Una cota superior para la cubicidad en términos de la boxicidad" , Discrete Mathematics , 309 (8): 2571–2574 , arXiv : math/0605486 , doi : 10.1016/j.disc.2008.04.011 , ISSN 0012-365X , S2CID 7837544  
  • Fishburn, Peter C. (1983-12-01), "Sobre la esfericidad y la cubicidad de los grafos" , Journal of Combinatorial Theory, Serie B , 35 (3): 309–318 , doi : 10.1016/0095-8956(83)90057-6 , ISSN 0095-8956 
  • Roberts, Fred S. (1969), "Sobre la boxicidad y la cubicidad de un grafo", en Tutte, WT (ed.), Avances recientes en combinatoria (PDF) , Academic Press, pp. 301–310 , ISBN  978-0-12-705150-5
Obtenido de " https://en.wikipedia.org/w/index.php?title=Cubicity&oldid=1357110496 "