Graphe croix

Graphe croix
Graphe croix
Cross graph.svg
Représentation du graphe croix.
Nombre de sommets 6
Nombre d'arêtes 5
Distribution des degrés 1 (4 sommets)
2 (1 sommet)
4 (1 sommet)
Rayon 2
Diamètre 3
Maille
Automorphismes 6
Nombre chromatique 2
Indice chromatique 4
Propriétés Biparti
Planaire
Distance-unité
Arbre

Le graphe croix est, en théorie des graphes, un graphe possédant 6 sommets et 5 arêtes.

Le nom de graphe croix est employé au sein de la classification de l'ISGCI (Information System on Graph Class Inclusions)[1].

Sommaire

Propriétés

Propriétés générales

Le diamètre du graphe croix, l'excentricité maximale de ses sommets, est 3, son rayon, l'excentricité minimale de ses sommets, est 2. Il ne possède aucun cycle, sa maille est donc infinie.

Il s'agit d'un graphe acyclique et connexe, c'est-à-dire d'un arbre. Il est donc 1-sommet-connexe et d'un 1-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il suffit de le priver d'un sommet ou d'une arête.

Toujours parce que le graphe croix est un arbre, il est possible de le tracer sur un plan sans qu'aucune de ses arêtes se croisent. Il est donc planaire. Il est également un graphe distance-unité : il peut s'obtenant à partir d'une collection de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1.

Coloriage

Le nombre chromatique du graphe croix est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'indice chromatique du graphe croix est 4. Il existe donc une 4-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Il est possible de compter les colorations distinctes du graphe croix. Cela donne une fonction dépendant du nombre de couleurs autorisé. C'est une fonction polynomiale et le polynôme qui lui est associé est qualifiée de polynôme chromatique. Ce polynôme de degré 6 admet pour racines tous les entiers positifs ou nuls strictement inférieurs à 2. Il est égal à : (x − 1)5x.

Propriétés algébriques

Le groupe d'automorphismes du graphe croix est un groupe d'ordre 6 isomorphe au groupe symétrique S3. Les automorphismes correspondent à toutes les permutations possibles des trois sommets de degré 1 qui sont reliés à l'unique sommet de degré 4.

Le polynôme caractéristique du graphe croix est : x2(x4 − 5x2 + 3). Le graphe croix est déterminé de façon unique par son spectre de graphe, l'ensemble des valeurs propres de sa matrice d'adjacence.

Voir aussi

Liens internes

Liens externes

Références

  1. (en) ISGCI (Information System on Graph Class Inclusions), List of small graphs (http://wwwteo.informatik.uni-rostock.de/isgci/smallgraphs.html).

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe croix de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Graphe distance-unité — Le graphe de Petersen est un graphe distance unité : il peut être tracé sur le plan avec des arêtes toutes de longueur 1 …   Wikipédia en Français

  • Graphe d'une relation — Correspondance et relation En algèbre générale (ou abstraite), le concept de correspondance, ou de relation, est une abstraction de notions telles que l’égalité, l’ordre alphabétique, ou la comparaison. De manière informelle, une relation dans un …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • chemin — [ ʃ(ə)mɛ̃ ] n. m. • 1080; du lat. pop. °camminus, mot gaulois I ♦ A ♦ (Concret) 1 ♦ Voie qui permet d aller d un lieu à un autre (⇒ route, voie); spécialt Bande déblayée assez étroite qui suit les accidents du terrain (opposé à route, allée).⇒… …   Encyclopédie Universelle

  • ARBRE — La distinction entre arbre et herbe remonte à une antiquité éloignée. Théophraste (vers 300 av. J. C.) en avait déjà fait la base de sa classification des végétaux, non sans quelque raison à en croire d’actuels botanistes. On sait que Hutchinson… …   Encyclopédie Universelle

  • Liste de fractales par dimension de Hausdorff — Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension topologique[1]. Sommaire 1… …   Wikipédia en Français

  • Liste De Fractales Par Dimension De Hausdorff — Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension topologique[1]. Sommaire 1… …   Wikipédia en Français

  • Liste de fractales — par dimension de Hausdorff Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension… …   Wikipédia en Français

  • Liste de fractales par dimension de hausdorff — Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension topologique[1]. Sommaire 1… …   Wikipédia en Français

  • Correspondance Et Relation — En algèbre générale (ou abstraite), le concept de correspondance, ou de relation, est une abstraction de notions telles que l’égalité, l’ordre alphabétique, ou la comparaison. De manière informelle, une relation dans un ensemble ( on dit aussi… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”