Clique (théorie des graphes)

In the mathematical area of graph theory, a clique (ˈkliːk or ˈklɪk) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied. Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term clique comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics. A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly. A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not maximal. A maximum clique of a graph, G, is a clique, such that there is no clique with more vertices. Moreover, the clique number ω(G) of a graph G is the number of vertices in a maximum clique in G. The intersection number of G is the smallest number of cliques that together cover all edges of G. The clique cover number of a graph G is the smallest number of cliques of G whose union covers the set of vertices V of the graph.

À 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 (80)

Cours associés (14)

Séances de cours associées (35)

Théorème de Turán

Le théorème de Turán est un résultat de théorie des graphes extrémaux découvert par Pál Turán. Ce théorème donne une borne supérieure sur le nombre d'arêtes dans les graphes ne contenant pas de cliques plus grosses qu'un paramètre r, et donne une caractérisation des graphes atteignant cette borne, ce sont les graphes de Turán. Ce résultat de 1941 a lancé la théorie des graphes extrémaux et possède de nombreuses preuves. Tout graphe G ayant n sommets, et ne contenant pas de clique de taille plus grande que r (i.

Coloration de graphe

thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.

Graphe parfait

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.

MATH-434: Lattice models

Lattice models consist of (typically random) objects living on a periodic graph. We will study some models that are mathematically interesting and representative of physical phenomena seen in the real

EE-619: Advanced topics in network neuroscience

The main goal of this course is to give the student a solid introduction into approaches, methods, and tools for brain network analysis. The student will learn about principles of network science and

COM-308: Internet analytics

Internet analytics is the collection, modeling, and analysis of user data in large-scale online services, such as social networking, e-commerce, search, and advertisement. This class explores a number

Programmes d'optimisation : Fonctions de coûts linéaires par pièce MGT-483: Optimal decision making

Couvre la formulation de programmes d'optimisation pour minimiser les fonctions de coûts linéaires à la pièce.

Analyse des données: Concentrations de KMnO4

Couvre l'analyse des concentrations de KMnO4 à l'aide de données provenant d'un fichier CSV.

Traitement des données CH-108(a): Chemistry Laboratory Work I

Couvre le traitement des données d'une expérience chimique à l'aide d'Excel.