thumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde.
En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle. Une définition équivalente est que tout cycle sans corde possède au plus trois sommets. Les graphes cordaux, aussi appelés graphes triangulés, sont un sous-ensemble des graphes parfaits.
On parle aussi de graphe triangulé.
Un graphe est cordal s'il ne contient pas de cycle induit de longueur 4 ou plus. Un cycle induit de longueur quatre ou plus est appelé un trou. Le terme «graphe triangulé» est aussi utilisé car chaque cycle doit être un triangle.
Un ordonnancement d'élimination parfaite d'un graphe est un ordonnancement des sommets du graphe tel que, pour tout sommet , l'ensemble formé par et ses voisins qui se trouvent après lui forment une clique. Un graphe est cordal si et seulement s'il possède un ordonnancement d'élimination parfaite .
thumb|Un graphe cordal à huit sommets, représenté comme le graphe d'intersection de huit sous-arbres d'un arbre à six nœuds
Une autre caractérisation des graphes cordaux faite par , utilise les arbres et leurs sous-arbres.
À partir d'une collection de sous-arbres d'un arbre , il est possible de définir un graphe sous-arbre qui est un graphe d'intersection avec un sommet par sous-arbre. Les arêtes relient les sous-arbres qui ont au moins un nœud en commun dans l'arbre . Comme Gavril l'a montré, les graphes sous-arbre sont exactement les graphes cordaux. Cette représentation forme une décomposition arborescente du graphe, où la hauteur du graphe vaut la taille de la plus grande clique du graphe moins un; la décomposition arborescente de n'importe quel graphe peut être vue de cette manière comme une représentation de comme un sous-graphe d'un graphe cordal.
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.
Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond
Un cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud. La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles. Cette famille de graphe a été introduite par plusieurs auteurs indépendamment dans les années 1970 sous divers noms, notamment D*-graphes, hereditary Dacey graphs et 2-parity graphs.
En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.
thumb|Exemple de graphe possédant une 3-clique (en rouge) : les trois sommets de ce sous-graphe sont tous adjacents deux-à-deux. thumb|Exemple de « biclique » : le graphe biparti complet K3,3. Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents. Une clique maximum d'un graphe est une clique dont le cardinal est le plus grand (c'est-à-dire qu'elle possède le plus grand nombre de sommets).
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
Le cours vise à faire découvrir les bases du design graphique, ses enjeux, ses différents domaines d'application, ses techniques et ses conventions. Il s'agit d'un enseignement pratique qui repose sur
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...
Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...
We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...