Estrella (teoría de grafos)
| Estrella | |
|---|---|
 La estrella S 7 . (Algunos autores indexan esto como S 8 ). | |
| Vértices | k + 1 |
| Bordes | k |
| Diámetro | 2 |
| Circunferencia | ∞ |
| Número cromático | 2 |
| Índice cromático | k |
| Propiedades | Distancia de unidad de árbol con borde transitivo Bipartito |
| Notación | S k |
| Tabla de gráficos y parámetros | |
En la teoría de grafos , una estrella S k es el grafo bipartito completo K 1, k : un árbol con un nodo interno yk sale (pero sin nodos internos yk + 1 sale 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 3 bordes se llama garra .
La estrella S k tiene un borde elegante cuando k es par y no cuando k es impar. Es un gráfico de cerillo de borde transitivo y tiene diámetro 2 (cuando k > 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 en k letras.
Las estrellas también pueden describirse como las únicas gráficas conectadas en las que como máximo un vértice tiene un grado mayor que uno.
Relación con otras familias de gráficos
Las garras son notables en la definición de gráficos sin garras , gráficos que no tienen ninguna garra como subgrafo inducido . [1] [2] También son uno de los casos excepcionales del teorema del isomorfismo del grafo de Whitney : en general, los grafos con grafos de líneas isomórficas son isomorfos en sí mismos, con la excepción de la garra y el triángulo K 3 . [3]
Una estrella es un tipo especial de árbol . Como ocurre con cualquier árbol, las estrellas pueden estar codificadas por 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]
Varias invariantes gráficas 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 gráfico de modo que cada árbol de cada bosque sea una estrella, [5] y el número cromático de estrellas de un gráfico es el número mínimo de colores necesarios para colorear sus vértices de tal forma una forma en que cada dos clases de color juntas forman un subgrafo en el que todos los componentes conectados son estrellas. [6] Los gráficos del ancho de rama 1 son exactamente los gráficos en los que cada componente conectado es una estrella. [7]
Otras aplicaciones
El conjunto de distancias entre los vértices de una garra proporciona un ejemplo de un espacio métrico finito que no se puede incrustar isométricamente en un espacio euclidiano de cualquier dimensión. [8]
La red en estrella , una red de computadoras modelada a partir del gráfico en estrella, es importante en la computación distribuida .
Una realización geométrica del gráfico de estrellas, 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 gráfico métrico en forma de estrella.
Referencias
 | Wikimedia Commons tiene medios relacionados con gráficos de estrellas . |
- ^ Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Gráficos sin garras - Una encuesta", Matemáticas discretas , 164 (1–3): 87–147, doi : 10.1016 / S0012-365X (96) 00045-3 , MR 1432221.
- ^ Chudnovsky, Maria ; Seymour, Paul (2005), "La estructura de los gráficos sin garras", Encuestas en combinatoria 2005 (PDF) , London Math. Soc. Lecture Note Ser., 327 , Cambridge: Cambridge Univ. Press, págs. 153-171, MR 2187738 .
- ^ Whitney, Hassler (enero de 1932), "Gráficos congruentes y la conectividad de los gráficos", American Journal of Mathematics , 54 (1): 150-168, doi : 10.2307 / 2371086 , hdl : 10338.dmlcz / 101067 , JSTOR 2371086 .
- ^ Gottlieb, J .; Julstrom, BA; Rothlauf, F .; Raidl, GR (2001). "Números de Prüfer: una mala representación 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.
- ^ Hakimi, SL; Mitchem, J .; Schmeichel, EE (1996), "Arboricidad en estrella de los gráficos", Matemáticas discretas. , 149 : 93–98, doi : 10.1016 / 0012-365X (94) 00313-8
- ^ Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Star coloring of graphs" , Journal of Graph Theory , 47 (3): 163–182, doi : 10.1002 / jgt.20029.
- ^ Robertson, Neil ; Seymour, Paul D. (1991), "Graph menores. X. Obstrucciones a la descomposición de árboles", Journal of Combinatorial Theory , 52 (2): 153-190, doi : 10.1016 / 0095-8956 (91) 90061-N.
- ^ Linial, Nathan (2002), "Espacios métricos finitos: combinatoria, geometría y algoritmos", Proc. Congreso Internacional de Matemáticos, Beijing , 3 , págs. 573–586, arXiv : math / 0304466 , Bibcode : 2003math ... 4466L
- Árboles (teoría de grafos)
- Familias paramétricas de gráficos
