Clique de taille k
En théorie des graphes, une clique est un sous-ensemble de sommets d'un graphe où chaque paire de sommets distincts est reliée par une arête. Le problème de la clique consiste à trouver la plus grande clique dans un graphe donné.
Formellement, si G est un graphe non orienté, une clique de G est un sous-ensemble C de sommets de G tels que chaque paire distincte de sommets dans C est reliée par une arête. La taille de la clique est simplement le nombre de sommets dans C.
Le problème de la clique peut être formulé comme suit : étant donné un graphe G, trouvez une clique C de taille maximale dans G.
En théorie, pour trouver une clique de taille p dans un graphe de n sommets, on doit examiner toutes les combinaisons possibles de p sommets parmi les n. Le nombre total de combinaisons possibles de p éléments parmi est défini par la formule : .
En pratique, il suffit de numéroter les éléments et de les ordonner selon l'ordre lexicographique pour que les combinaisons s'ordonnent d'elles-mêmes. Voici un exemple pour p = 6 et n = 49.
Cette structuration des combinaisons de p éléments choisis parmi N reste valable ∀p et ∀N, 0 < p <= N.
Bien entendu, Il n'est pas nécessaire de lister toutes les combinaisons à partir du rang 1 dès lors que l'on a établi, comme on le constate sur la figure ci-dessus, que l'ordonnancement des éléments des combinaisaons entraine l'ordonnancement des combinaisons .
En regardant l'exemple de code ci-après, pour p = 6 et N = 49 et en n'oubliant pas de fixer les bornes comme je le fais, il vous sera facile de lister des plages de combinaisons que vous ferez démarrer avec le premier élément que vous voudriez et avec le nombre de combinaisons souhaitées.
Pour le code ci-dessus, valable pour des combinaisons de 6 éléments choisis parmi 49, en fixant $dep = 42 et $dep2 = 44, voici ce que vous obtiendrez :
Pour des valeurs de p et de N différentes, souvenez-vous, en générant votre code que le nombre de boucle " for" est toujours égal à p. En générant votre code pour des valeurs supérieures à 100, vous ferez moins d'erreurs.
► Notez bien que notre propre code est inspiré du code que nous vous donnons en exemple.
Vous constaterez 4 choses :
- d'abord qu'il n'a pas été nécessaire de partir du rang 1.
- vous pouvez faire démarrer le listage des combinaisons à partir d'un rang donné;
- vous pouvez arrêter le listage des combinaisons où vous voulez
- ensuite, vous n'avez pas eu besoin de mémoriser les combinaisons précédentes
En somme,vous avez gagné du temps et de l'espace.
Vous avez donc dans les mains un « oracle », cette entité hypothétique que les théoriciens de la complexité utilisent pour pouvoir finaliser leurs théories. Avec cet « oracle » vous pouvez parfaitement obtenir une plage de combinaisons ordonnées et délimitées par une borne basse et une borne haute.
Complexité de la recherche de k éléments, k <= p, dans une combinaison dont les éléments sont ordonnés :
La complexité de la recherche de k éléments dans une combinaison ordonnée de p éléments choisis parmi N, les p éléments étant ordonnés selon l'ordre lexicographique, se fera en k * log2(p) opérations (recherche dichotomique).
Complexité de la recherche de k éléments, k <= p, d'une combinaison dans l'intervalle [1, ] :
La complexité de la recherche de k éléments d'une combinaison ordonnée de p éléments choisis parmi N, dans la liste ordonnée des combinaisons de l'intervalle [1, ], s'effectuera en k * log2(p) * log2( ) opérations (Recherche dichotomique).
Complexité de la recherche d'une combinaison de k éléments, k <= p dans l'intervalle |1,2N]:
Prenons d'abord l'exemple de N = 10, ce qui nous donne l'intervalle [1, 1024 = 210]. Une image valant mieux que tous les discours, voici la numérotation des combinaisons
La complexité de la recherche de k éléments d'une combinaison ordonnée de p éléments choisis parmi N dans la liste ordonnée des combinaisons de l'intervalle [1, 2N] s'effectuera en N * k * log2(p) * log2( ) opérations.