Graphe complet | EPFL Graph Search

Ê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 GraphSearch.

Découvrez-en plus sur les applications Graph.

En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens). Un graphe complet est un graphe dont tous les sommets sont adjacents. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre n, que l'on note . Dans un graphe G quelconque, on appelle clique un sous-ensemble de sommets induisant un sous-graphe complet de G. Rechercher une clique de taille maximum dans un graphe est un problème classique en théorie des graphes. Il est NP-complet. La notion de graphe biparti complet existe également. Mais un graphe biparti complet n'est pas un graphe complet. Le nombre d'arêtes de est : Le premier terme s'obtient en remarquant que la suppression d'un premier sommet de entraîne la suppression de arêtes, la suppression d'un deuxième sommet, la suppression de arêtes, et celle d'un i-ème sommet arêtes. Le deuxième terme s'obtient par la même opération en marquant les arêtes au lieu de les supprimer, chaque arête est alors marquée deux fois et l'on fait marquages par sommet (c'est la formule générale de la demi-somme des degrés). On peut également obtenir cette formule en voyant le nombre d’arêtes comme le nombre de couples distincts que l’on peut former avec nœuds, soit arêtes, ce qui vaut bien . Le graphe complet est symétrique : il est sommet-transitif, arête-transitif et arc-transitif. Cela signifie que son groupe d'automorphismes agit transitivement sur l'ensemble de ses sommets, de ses arêtes et de ses arcs. Ce groupe d'automorphismes est de cardinal n! et est isomorphe au groupe symétrique . Le polynôme caractéristique du graphe complet est : . Ce polynôme caractéristique n'admet que des racines entières. Le graphe complet est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers. Le graphe est le plus petit graphe non planaire.

À 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.

Publications associées (67)

Personnes associées (17)

Unités associées (8)

Concepts associés (29)

Cours associés (15)

Séances de cours associées (34)

Graphe (mathématiques discrètes)

Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Graphe planaire

Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.

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

EE-548: Audio engineering

This lecture is oriented towards the study of audio engineering, with a special focus on room acoustics applications. The learning outcomes will be the techniques for microphones and loudspeaker desig

COM-516: Markov chains and algorithmic applications

The study of random walks finds many applications in computer science and communications. The goal of the course is to get familiar with the theory of random walks, and to get an overview of some appl

Chaînes et applications Markov COM-516: Markov chains and algorithmic applications

Explore les chaînes de Markov, le modèle Ising, l'algorithme Metropolis et la dynamique Glauber.

Ramsey Theory : Changements et colorations MATH-467: Probabilistic methods in combinatorics

Explore la théorie de Ramsey, les altérations, les colorations dans les graphiques, les correspondances monochromatiques et la signification des grandes cliques.

Subgraphs vs Induced Subgraphs

Distingue entre les sous-graphes et les sous-graphes induits en théorie des graphes, illustrant la construction d'arbres couvrants minimes.

Metastability of the Potts Ferromagnet on Random Regular Graphs

Jean Bernoulli Ravelomanana

We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...

SPRINGER2023

AiiDA-defects: an automated and fully reproducible workflow for the complete characterization of defect chemistry in functional materials

Nicola Marzari, Sokseiha Muy, Conrad Johnston

Functional materials that enable many technological applications in our everyday lives owe their unique properties to defects that are carefully engineered and incorporated into these materials during processing. However, optimizing and characterizing thes ...

IOP Publishing Ltd2023

Superior visible light-mediated catalytic activity of a novel N-doped, Fe3O4-incorporating MgO nanosheet in presence of PMS: Imidacloprid degradation and implications on simultaneous bacterial inactivation

Stefanos Giannakis, Jérémie Decker

Impressive Imidacloprid (IMD) degradation and bacterial inactivation were attained through the photocatalytic activation of peroxymonosulfate (PMS) via a novel, N-doped MgO@Fe3O4, under visible light. After complete characterization (XPS, XRD, FT-IR, FE-SE ...

ELSEVIER2022