clique

SOMMAIRE :

1)Introduction

2 )Définition d'un graphe et d'une Clique

3 )Problèmes de Clique

4 )Des algorithmes pour trouver la clique maximal

5) QCM

I) INTRODUCTION

En algorithme il existe des problèmes qu'on ne peut pas résoudre en temps polynomial. Ils sont appelés les Np-complets dont le problème de la clique maximale fait partie

II) DÉFINITION:

graphe G est un couple (V, E) où V est un ensemble de sommets et E est
un ensemble d’arêtes .

Dans un graphe G=(V,E) ,une clique de G est un sous-ensemble complet de nœuds du graphe, autrement dit un ensemble E’ des sommets C ⊆ V tel que pour tout u,v ∈ C, {u,v} ∈ E.
C’est-à-dire que chacun des nœuds du sous-ensemble E’ est connecté avec l’intégralité des autres.
Une clique qui ne contient qu’un seul sommet est appelée une clique triviale.
Une clique C est maximale si elle n’est pas incluse dans une clique de taille supérieure.

Exemple :
La figure 1 représente un graphe qui contient une 3-clique distingué par les sommets rouges .

Figure 1 : une 3-clique

III) LES PROBLÈMES:

La clique, permet d’extraire de l’information d’un graphe. Cependant, trouver ces structures est considéré comme un problème difficile.
Dans la recherche de cliques, deux grands problèmes existent :

  1. Le problème de la clique maximum :
    Une clique C de taille k ( k est le nombre de nœuds) est un sous-ensemble complet de nœuds v ∈ E.
    Le problème de clique maximal consiste à trouver la clique dont la taille k est la plus grande pour le graphe G (s’il y en a plusieurs avec la même taille, il suffit juste d’en trouver une).
  2. Le problème d’énumération de cliques maximales :
    Le problème d’énumération de cliques maximales consiste à lister l’ensemble des cliques maximales du graphe G.
    Dans le cas des grands graphes ces problèmes deviennent donc difficiles à traiter car les données en entrée sont nombreuses (le nombre de nœuds et le nombre d’arêtes) et le temps d’exécution est exponentiel avec la taille de ces données.
    Dans ce cas, plusieurs solutions ont été envisagées pour trouver des solutions non-exactes mais proches d’un optimal avec des heuristiques. Pour engendrer les cliques de tailles maximales de graphe donné, on peut implémenter un algorithme naïf nommé Recherche exhaustive qui consiste à examiner tous les sous-graphes de
    taille k dans un graphe à n sommets et tester s’ils forment une clique. Mais le problème rencontré est le nombre des sous graphes qui peut être très élevé et égale à la formule 1.
{n \choose k}={\frac  {n!}{k!(n-k)!}}

IV)DES ALGORITHMES POUR TROUVER LA CLIQUE MAXIMALE

un algorithme polynomial qui étant donnés un graphe G et un sommet u, retourne une clique maximale contenant u dans G.

Entrée : un graphe G, un sommet u
Sortie : Un ensemble de sommets C
Clique Max(G,u) :
C ← {u} ; // O(1) opérations
Pour tout sommet v faire: // la boucle est exécutée O(|V|) fois
b ← True ; //b un boolean O(1) opérations
Pour chaque sommet x de C : // la boucle est exécutée O(|V|) fois max
si x n’est pas voisin de v alors:
b ← False ; // O(1) opérations
si b == True alors: // O(1) opérations
C← C ∪ {v} ; // O(1) opérations {v} Retourner C ;

Complexité : O(|V|²) opérations.

Nous appelons une partition en cliques maximales du graphe G = (V, E), une partition des sommets
V en sous-ensembles disjoints C = {C 1 , . . . , C k } tels que
1. { C 1,C2, .... , Ck} = V ;
2. pour tout couple (i, j) tel que 1 ≤ i < j ≤ k, nous avons C i ∩ C j = ∅ ; ;
3. chaque sous-graphe induit par C i dans G est une clique maximale ;

un algorithme polynomial qui retourne une partition en cliques maximales de G.

Entrée : un graphe G
Sortie : Un ensemble de sommets C
Clique Max(G) :
C ← Ø ;
Pour chaque sommet u de G faire: // la boucle est exécutée O(|V|) fois
T ← Clique Max (G,u) ;
Si (|T|>|C|) alors :
C ← T ;
Retourner C ;

Complexité : O(|V|^3) opérations

Le problème (de décision) de la clique prend en entrée un graphe G et un entier k et détermine si G contient une clique de taille k.

Entrée : un graphe G, un entier k
Sortie : Un boolean
Clique Max(G,k) :
Retourner k>= Clique Max(G) ;

Complexité : O(|V|^3) opérations

V)QCM:

Question 1. Dans une clique C de n sommets, donner une couverture de sommets de plus petite cardinalité.
a) n²
b) n
c) n-1
d) n(n-1)/2

Considérons le graphe suivant :

Question 2 : L’ensemble S = {2,4,5} est une clique ?
a)Vrai
b)Faux

Est ce de cardinalité maximale?
a)Vrai
b)Faux

question 3: Un graphe à n sommets dont tous les sommets sont à k degré est un k-clique? a)Vrai b)faux

question 4: Un graphe complet à n sommets possède une clique maximale ?a) n clique b)(n-1)clique

question 5: Le graphe biparti k3,3 est : a)3-clique b) 6-clique c)possède pas de clique s

3 Cliquer pour recommander cet article