Graphe cubique

En théorie des graphes, une branche des mathématiques, un graphe cubique est un graphe régulier de degré 3. En d'autres termes, c'est un graphe dans lequel il y a exactement trois arêtes incidentes à chaque sommet. Le graphe complet K4 est le plus petit graphe cubique. Le graphe biparti complet K3,3 est le plus petit graphe cubique non-planaire. Le graphe de Petersen est le plus petit graphe cubique de maille 5. Le graphe de Heawood est le plus petit graphe cubique de maille 6. Le graphe de Frucht est le plus petit graphe cubique à être un graphe asymétrique. Le 110-graphe de Iofinova-Ivanov est un graphe 3-régulier cubique biparti et hamiltonien. Une conséquence du lemme des poignées de main est que tout graphe cubique a un nombre pair de sommets. D'après le théorème de Brooks, les sommets d'un graphe cubique peuvent être coloriés avec trois couleurs (ou moins) de telle sorte que deux sommets adjacents ne soient pas de la même couleur, sauf dans le cas du graphe tétraédrique . Un graphe bicubique est un graphe biparti régulier de degré 3, c'est-à-dire un graphe cubique dont les sommets peuvent être coloriés avec deux couleurs seulement. Complete graph K4 4COL.svg|Le graphe complet K_4 est le seul graphe cubique nécessitant 4 couleurs Frucht graph 3COL.svg|Coloration du [[graphe de Frucht]] avec 3 couleurs Graph K3-3.svg|K_{3,3} est un graphe bicubique, 2 couleurs suffisent PetersenBarveniHran.svg|Les arêtes du graphe de Petersen, un snark, ont besoin de 4 couleurs D'après le théorème de Vizing, les arêtes d'un graphe cubique peuvent être colorées avec 3 ou 4 couleurs sans que deux arêtes de même couleur ne soient incidentes au même sommet. Les snarks sont les graphes cubiques connexes et sans isthme qui ont besoin de 4 couleurs. Le théorème de Petersen précise que tout graphe cubique sans isthme possède un couplage parfait. En d'autres termes, si, dans un graphe cubique, toute arête appartient à un cycle, alors il existe un ensemble d'arêtes qui sont incidentes à tous les sommets, chaque sommet n'étant l'extrémité que d'une seule de ces arêtes.

À propos de ce résultat

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.

Concepts associés (57)

Cours associés (7)

Séances de cours associées (43)

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

PHYS-512: Statistical physics of computation

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and

MATH-335: Coxeter groups

Study groups generated by reflections

Graphe symétrique

En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe : tel que et . En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif. Par définition, un graphe symétrique sans sommet isolé est sommet-transitif et arête-transitif.

Coloration des arêtes d'un graphe

thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.

Snark (graphe)

En théorie des graphes, une branche des mathématiques, un snark est un graphe cubique connexe, sans isthme et d'indice chromatique égal à 4. En d'autres termes, c'est un graphe dans lequel chaque sommet a trois voisins, et dont les arêtes ne peuvent pas être colorées avec seulement 3 couleurs sans que deux arêtes de même couleur ne se rencontrent en un même sommet (d'après le théorème de Vizing, l'indice chromatique d'un graphe cubique est 3 ou 4). Pour éviter les cas triviaux, on exige souvent de plus que les snarks aient une maille d'au moins 5.

Cognition sociale CS-411: Digital education

S'oriente vers la connaissance sociale, l'efficacité de l'apprentissage collaboratif, le consensus de groupe et le rôle de la technologie dans l'amélioration des interactions.

Théorie de l'information: Bases PHYS-512: Statistical physics of computation

Couvre les bases de la théorie de l'information, de l'entropie et des points fixes dans les coloriages graphiques et le modèle Ising.

Transformateurs Graph-to-Graph : Encodage graphique sensible à la syntaxe EE-608: Deep Learning For Natural Language Processing

Introduit l'architecture Graph-to-Graph Transformer sensible à la syntaxe pour un conditionnement efficace sur les graphes de dépendance syntaxiques.