$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Lien copié  ✅
Dictionnaire de mathématiques > Mathématiques discrètes > Théorie des graphes >

Clique

Une clique d'un graphe non-orienté $G$ est un sous-ensemble de sommets de $G$ deux à deux adjacents.

Autrement dit, c'est un sous ensemble $C$ de sommets tel que le sous-graphe de $G$ induit par $C$ est complet. Le terme de clique est parfois utilisé pour désigner le sous-graphe induit et non plus seulement ses sommets.

Si la clique contient $p$ sommets, on parle de p-clique ou encore de clique de cardinalité $p$.

Une clique est maximale si elle n'est pas incluse dans une clique de cardinal plus grand, et elle est maximum si il n'existe pas d'autre clique de cardinal plus grand dans le graphe.

Le nombre de clique d'un graphe est alors défini comme le cardinal de ses cliques maximum. En particulier, le nombre chromatique est supérieur ou égal au nombre de clique.

Différentes cliques sur un même graphe

Une biclique d'un graphe non-orienté $G$ est un sous-ensemble $C$ de sommets de $G$ tel que le sous-graphe de $G$ induit par $C$ est biparti complet, c'est-à-dire s'il existe une partition de $C$ en deux sous-ensembles $U$ et $V$ tels que chaque sommet de $U$ est relié à chaque sommet de $V.$

Consulter aussi
Recherche alphabétique
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Recherche thématique
  • Algèbre
  • Analyse
  • Applications
  • Arithmétique
  • Probabilité et statistiques
  • Géométrie
  • Fondements
  • Histoire
  • Mathématiques discrètes
  • Mathématiques interactives