Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Factorisation de graphes
Résumé
vignette|200x200px| Une 1-factorisation du graphe de Desargues : chaque classe de couleur est un 1-facteur.
droite|vignette|200x200px| Le graphe de Petersen peut être partitionné en un 1-facteur 1 (en rouge) et un 2-facteur 2 (en bleu). Cependant, le graphe n'est pas 1-factorisable.
En théorie des graphes, un facteur d'un graphe G est un graphe partiel, c'est-à-dire un graphe qui a le même ensemble de sommets que G et dont les arêtes sont contenues dans celles de G. Un k -facteur d'un graphe est un graphe partiel k-régulier, et une k-factorisation partitionne les arêtes du graphe en des k-facteurs disjoints. Un graphe G est dit k-factorisable s'il admet une k-factorisation. En particulier, un 1-facteur est une couplage parfait et une 1-factorisation d'un graphe k-régulier est une coloration des arêtes avec k couleurs. Un 2-facteur est une collection de cycles qui couvre tous les sommets du graphe.
Un graphe qui est 1-factorisable (c'est-à-dire qui admet une 1-factorisation) est un graphe régulier. La réciproque est fausse : tous les graphes réguliers ne sont pas 1-factorisables. Un graphe k -régulier est 1-factorisable 1 s'il a un indice chromatique égal à k ; des exemples de tels graphes comprennent notamment :
Tout graphe biparti régulier. Le théorème de mariage de Hall montre en effet qu'un graphe biparti k-régulier contient un couplage parfait. On peut alors supprimer ce couplage parfait et on obtient a graphe biparti ( k − 1)-régulier, auquel on applique le même raisonnement.
Tout graphe complet avec un nombre pair de nœuds (voir aussi ci-dessous ).
Il existe également des graphes k-réguliers qui ont un indice chromatique k + 1, et ces graphes ne sont pas 1-factorisables ; des exemples de tels graphies sont :
Tout graphe régulier avec un nombre impair de sommets.
Le graphe de Petersen .
vignette|200x200px| Une 1-factorisation de K 8 ; chaque 1-facteur consiste en une arête du centre à un sommet d'un heptagone avec les trois arêtes parallèles possibles.
Une 1-factorisation d'un graphe complet correspond à des couplage dans un tournoi toutes rondes .
Source officielle
À 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.
Cours associés (8)
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-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
FIN-406: Macrofinance
This course provides students with a working knowledge of macroeconomic models that explicitly incorporate financial markets. The goal is to develop a broad and analytical framework for analyzing the
Publications associées (24)
Finding Paths for Explainable MOOC Recommendation: A Learner Perspective
Jibril Albachir Frej, Tatjana Nazaretsky
The increasing availability of Massive Open Online Courses (MOOCs) has created a necessity for personalized course recommendation systems. These systems often combine neural networks with Knowledge Graphs (KGs) to achieve richer representations of learners ...
2023