Conde estrella
Un gráfico de estrella es un gráfico conectado en el que todos los bordes se originan en el mismo vértice. Se suele denotar una estrella con un vértice , lo que se denomina el orden de la estrella.
Otras definiciones
- S k es el grafo bipartito completo K 1, k . [1] .
- un árbol con un nodo interno y k hojas. Además, algunos autores definen S k como un árbol de orden k con un diámetro máximo de 2; entonces el gráfico de estrellas k > 2 tiene k - 1 hojas.
Una estrella gráfica con tres costillas se llama pata o garra [2] ( ing. garra ).
El gráfico de estrellas S k tiene la gracia de los vértices ., cuando k es par, y no, si k es impar.
Un gráfico de estrella también se puede describir como un gráfico conexo , en el que como máximo un vértice tiene un grado mayor que uno.
Relación con otros tipos de gráficos
Los gráficos de garras son importantes en la definición de gráficos sin garras , gráficos que no tienen subgrafos que son garras [3] [4] .
El gráfico de estrellas es un tipo especial de árbol . Como cualquier árbol , un gráfico estelar se puede codificar utilizando la secuencia de Prüfer ; la sucesión de Prufer para el gráfico estelar K 1, k consta de k − 1 copias del vértice central [5] .
Otros usos
El conjunto de distancias entre los vértices de un gráfico de garra es un ejemplo de un espacio métrico que no se puede incrustar isométricamente en un espacio euclidiano de cualquier dimensión [6] .
La topología de la red informática Zvezda , construida en forma de gráfico de estrellas, juega un papel importante en la computación distribuida .
Notas
- ↑ Materiales educativos públicos de VSUES . Consultado el 3 de octubre de 2016. Archivado desde el original el 5 de octubre de 2016.
- ↑ VA Evstigneev, V.N. Kasyanov. Diccionario de grafos en informática. - Novosibirsk. — (Diseño y optimización de programas). - ISBN 978-591124-036-3 .
- ↑ Faudree, Ralph ; Flandrin, Evelyne & Ryjáček, Zdeněk (1997), Gráficos sin garras: una encuesta , Matemáticas discretas , volumen 164 (1–3): 87–147 , DOI 10.1016/S0012-365X(96)00045-3 .
- ↑ Chudnovsky, Maria & Seymour, Paul (2005), La estructura de los gráficos sin garras , Surveys in combinatorics 2005 , vol. 327, Matemáticas de Londres. soc. Lecture Note Ser., Cambridge: Universidad de Cambridge. Prensa, pág. 153–171 , < http://www.columbia.edu/~mc2775/claws_survey.pdf > Archivado el 23 de octubre de 2012 en Wayback Machine .
- ↑ Gottlieb, J.; Julstrom, BA; Rothlauf, F. & Raidl, GR (2001), Números de Prüfer: Una mala representación de los árboles de expansión para la búsqueda evolutiva , Proc. Conferencia de Computación Genética y Evolutiva , Morgan Kaufmann, p. 343–350 , < http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf > . Consultado el 4 de enero de 2013. Archivado el 26 de septiembre de 2006 en Wayback Machine .
- ↑ Linial, Nathan (2002), Espacios métricos finitos: combinatoria, geometría y algoritmos, Proc. Congreso Internacional de Matemáticos, Beijing , vol. 3, pág. 573–586