Worldlex Wiki En théorie des graphes , l' étoile est le graphe biparti complet , c'est-à-dire un arbre possédant un nœud interne et comme l'arbre d' ordre possède feuilles.
Une étoile à 3 bords est appelée une griffe .
L'étoile est gracieuse sur les arêtes lorsque est impair. C'est un graphe en allumettes transitif sur les arêtes , et son diamètre est de 2 (lorsque ).
Une étoile est un type particulier d' arbre . Comme tout arbre, les étoiles peuvent être codées par une séquence de Prüfer ; la séquence de Prüfer pour une étoile est constituée de copies du sommet central.
Plusieurs invariants de graphes sont définis en termes d'étoiles. L'arboricité stellaire est le nombre minimal de forêts dans lesquelles un graphe peut être partitionné de sorte que chaque arbre de chaque forêt soit une étoile Le nombre chromatique stellaire d'un graphe est le nombre minimal de couleurs nécessaires pour colorer ses sommets de telle sorte que chaque paire de couleurs forme un sous-graphe dont toutes les composantes connexes sont des étoiles . Les graphes de largeur de branche 1 sont précisément les graphes dont chaque composante connexe est une étoile
Autres applications
L'ensemble des distances entre les sommets d'une griffe fournit un exemple d' espace métrique fini qui ne peut pas être plongé isométriquement dans un espace euclidien de toute dimension.
Le réseau en étoile , un réseau informatique modélisé d'après le graphe en étoile, est important dans le calcul distribué .
Une réalisation géométrique du graphe en étoile, obtenue en identifiant les arêtes à des intervalles de longueur fixe, sert de modèle local des courbes en géométrie tropicale . Une courbe tropicale est définie comme un espace métrique localement isomorphe à un graphe métrique en étoile.