stringtranslate.com

Estrella (teoría de grafos)

En teoría de grafos , una estrella S k es el grafo bipartito completo K 1, k  : un árbol con un nodo interno y k hojas (pero sin nodos internos y k + 1 hojas cuando k ≤ 1 ). Alternativamente, algunos autores definen S k como el árbol de orden k con diámetro máximo 2; en cuyo caso una estrella de k > 2 tiene k − 1 hojas.

Una estrella con tres aristas se llama garra .

La estrella S k tiene aristas elegantes cuando k es par y no cuando k es impar. Es un grafo de cerillas transitivo de aristas y tiene diámetro 2 (cuando l > 1 ), circunferencia ∞ (no tiene ciclos), índice cromático k y número cromático 2 (cuando k > 0 ). Además, la estrella tiene un gran grupo de automorfismos, es decir, el grupo simétrico de k letras.

Las estrellas también pueden describirse como los únicos gráficos conexos en los que como máximo un vértice tiene grado mayor que uno.

Relación con otras familias de gráficos

Las garras son notables en la definición de grafos sin garras , grafos que no tienen ninguna garra como subgrafo inducido . [1] [2] También son uno de los casos excepcionales del teorema de isomorfismo de grafos de Whitney : en general, los grafos con grafos lineales isomorfos son en sí mismos isomorfos, con la excepción de la garra y el triángulo K 3 . [3]

Una estrella es un tipo especial de árbol . Como cualquier árbol, las estrellas pueden codificarse mediante una secuencia de Prüfer ; la secuencia de Prüfer para una estrella K 1, k consta de k − 1 copias del vértice central. [4]

Varios invariantes de grafos se definen en términos de estrellas. La arboricidad de estrellas es el número mínimo de bosques en los que se puede dividir un grafo de manera que cada árbol de cada bosque sea una estrella [5] , y el número cromático de estrellas de un grafo es el número mínimo de colores necesarios para colorear sus vértices de manera que cada dos clases de color juntas formen un subgrafo en el que todos los componentes conectados sean estrellas [6] . Los grafos con ancho de rama 1 son exactamente los grafos en los que cada componente conectado es una estrella [7] .

Los gráficos estelares S 3 , S 4 , S 5 y S 6 .

Otras aplicaciones

El conjunto de distancias entre los vértices de una garra proporciona un ejemplo de un espacio métrico finito que no puede integrarse isométricamente en un espacio euclidiano de cualquier dimensión. [8]

La red en estrella , una red informática modelada según el gráfico en estrella, es importante en la computación distribuida .

Una realización geométrica del grafo estrella, formada mediante la identificación de los bordes con intervalos de cierta longitud fija, se utiliza como modelo local de curvas en geometría tropical . Una curva tropical se define como un espacio métrico que es localmente isomorfo a un grafo métrico en forma de estrella.

Véase también

Referencias

  1. ^ Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Gráficos sin garras: un estudio", Discrete Mathematics , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , MR  1432221.
  2. ^ Chudnovsky, Maria ; Seymour, Paul (2005), "La estructura de los grafos sin garras", Encuestas en combinatoria 2005 (PDF) , London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, págs. 153–171, MR  2187738.
  3. ^ Whitney, Hassler (enero de 1932), "Gráficos congruentes y conectividad de gráficos", American Journal of Mathematics , 54 (1): 150–168, doi :10.2307/2371086, hdl : 10338.dmlcz/101067 , JSTOR  2371086.
  4. ^ Gottlieb, J.; Julstrom, BA; Rothlauf, F.; Raidl, GR (2001), "Números de Prüfer: una representación pobre de árboles de expansión para la búsqueda evolutiva" (PDF) , GECCO-2001: Actas de la Conferencia de Computación Genética y Evolutiva , Morgan Kaufmann, págs. 343–350, ISBN 1558607749, archivado desde el original (PDF) el 26 de septiembre de 2006
  5. ^ Hakimi, SL; Mitchem, J.; Schmeichel, EE (1996), "Arboricidad estelar de grafos", Discrete Math. , 149 (1–3): 93–98, doi : 10.1016/0012-365X(94)00313-8
  6. ^ Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Coloración estelar de gráficos", Journal of Graph Theory , 47 (3): 163–182, doi :10.1002/jgt.20029.
  7. ^ Robertson, Neil ; Seymour, Paul D. (1991), "Grafos menores. X. Obstrucciones a la descomposición en árboles", Journal of Combinatorial Theory , 52 (2): 153–190, doi : 10.1016/0095-8956(91)90061-N.
  8. ^ Linial, Nathan (2002), "Espacios métricos finitos: combinatoria, geometría y algoritmos", Proc. Congreso Internacional de Matemáticos, Pekín , vol. 3, págs. 573–586, arXiv : math/0304466 , Bibcode :2003math......4466L