Les graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2.
Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique.
Nombre chromatique. Le nombre chromatique du cycle est égal à 3 si n est impair, à 2 sinon. En d'autres termes, est biparti si et seulement si n est pair.
Connexité. Par construction est connexe. Il est facile de constater qu'il est 2-sommet-connexe (c'est-à-dire qu'il cesse d'être connexe uniquement quand on lui supprime 2 sommets). Il est également 2-arête-connexe.
Hamiltonicité. L'unique cycle contenu dans est un cycle hamiltonien. Le graphe cycle est donc hamiltonien.
Planarité. est un graphe planaire.
Eulérien. Étant 2-régulier, le cycle est eulérien par le théorème d'Euler-Hierholzer.
Line graph. Le line graph de est isomorphe à .
Le graphe cycle peut être dessiné comme un polygone régulier à n sommets. Les isométries de ce polygone s'avèrent alors êtres des automorphismes de . De là découlent l'arête-transitivité et la sommet-transitivité. est donc un graphe symétrique. Tous ses sommets et toutes ses arêtes jouent le même rôle en termes d'isomorphisme de graphe.
Il est facile de constater que seules les isométries de ce polygone sont des automorphismes valides de . Le groupe d'automorphismes du graphe cycle est donc isomorphe à celui des isométries du polygone régulier à n sommets, à savoir le groupe diédral , groupe d'ordre 2n.
Le graphe cycle est un graphe de Cayley avec :
et
Le polynôme caractéristique de la matrice d'adjacence du graphe cycle est (dont toutes les racines sont doubles sauf 2 et éventuellement -2).
est le graphe triangle.
est le graphe carré, il est isomorphe à l'hypercube ou a la grille G(2,2).
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Les graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2. Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique. Nombre chromatique.
En théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble. Plus précisément, il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que chaque sommet de est relié à chaque sommet de . Si le premier ensemble est de cardinal m et le second ensemble est de cardinal n, le graphe biparti complet est noté . Si m = 1, le graphe complet biparti K1,n est une étoile et est noté .
En mathématiques, plus spécialement en théorie des graphes, un graphe nul désigne soit un graphe d'ordre zéro (i.e. sans sommets), soit un graphe avec sommets mais sans arêtes (on parle aussi dans ce dernier cas de graphe vide). Lorsqu'un graphe nul contient des sommets tous isolés, on le note où représente le nombre de sommets du graphe. La taille (i.e. le nombre d'arêtes ou d'arcs) d'un graphe nul est toujours zéro. L'ordre (i.e. le nombre de sommets) d'un graphe nul n'est pas nécessairement zéro.
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
Concepts de base de l'analyse fonctionnelle linéaire: opérateurs bornés, opérateurs compacts, théorie spectrale pour les opérateurs symétriques et compacts, le théorème de Hahn-Banach, les théorèmes d
The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch
Explore les applications linéaires dans la représentation R2 et matricielle, y compris la base, les opérations et l'interprétation géométrique des transformations.