Discussion:Clique (théorie des graphes)

NP (non polynomial)

Je ne suis pas d'accord avec la mention entre parenthèse NP faisant référence à Non-deterministic polynomial donc réalisé en temps polynomial sur une machine de Turing non déterministe mais je préfère en discuter ici plutôt que de modifier, étant donné que NP = P est non encore prouvée ou réfutée à ce jour.

Clique et musique

Bonjour,

Cet article étant résolument orienté vers l'informatique ou les mathématiques, je propose de retirer la mention sur la musique militaire - quoique tout à fait pertinente dans l'acception militaire de la clique (cf. par exemple la définition de l'ATILF pour clique). Un article pourra bien entendu être produit par rapport aux différents sens de ce terme, avec l'introduction d'une page d'homonymie. On pourra même légitimement discuter d'une page d'entrée sur le terme "clique", couplée à des pages secondaires, dont l'une concernerait l'acception dans la théorie des graphes, avec par exemple pour titre "clique (théorie des graphes)" à l'instar d'autres notions.

Cordialement --nha de Lyon. 27 juillet 2006 à 23:55 (CEST)

Bonjour,

Suite à l'avis implicite de Taguelmoust (cf. historique de modification de l'article), auquel j'adresse mes excuses si ma précédente manœuvre a été perçue comme tendant à une certaine radicalité, et dans le même esprit de maintien des sens du terme ciblé, j'ai ajouté (créé) 2 titres de section distinguant les différents sens de clique.

Une perspective consensuelle serait de créer un article par homonymie (typiquement : Clique (graphe) et Clique (musique)) ; le présent article servirait alors d'index de liens vers ces différents liens, à l'instar des autres cas d'homonymie.

Cordialement --nha de Lyon 28 août 2006 à 02:43 (CEST)

Séparer l'algorithmique

Bonjour,

que pensez-vous d'un article séparé pour le problème de la clique maximum ?

--Roll-Morton (discuter) 1 novembre 2013 à 20:33 (CET)

LA clique maximale

Connaissant très peu de choses en théorie des graphes, je m'étonne cependant, peut-être à tord, qu'il soit question dans cet article de LA clique maximale (l'adjectif maximale devrait être préféré à maximum, selon certains dictionnaires), alors qu'il me semble qu'il peut en exister plus d'une. JChG (discuter) 30 novembre 2013 à 11:29 (CET)

C'est vrai que c'est mal dit, mais l'abus de langage est courant, "le problème de la clique maximum" notamment est une expression assez courante je crois. Je vais rajouter une ligne pour préciser. En ce qui concerne maximum et maximale, les deux sont utilisés et je ne sais jamais ce qui est correct. Je crois que la tendance en info et en maths est de s'aligner sur l'anglais : maximum pour un élément de cardinal maximum et maximal pour un élément maximal pour l'inclusion (c'est ce que je fais le plus souvent, mais sans grande conviction). --Roll-Morton (discuter) 30 novembre 2013 à 13:45 (CET)

En fait j'ai l'impression que cette dernière partie est plus ou moins redondante avec la partie précédente...--Roll-Morton (discuter) 30 novembre 2013 à 13:52 (CET)

NP-complet vs NP-difficile

Y a-t-il une raison de considérer le problème de la plus grande Clique comme NP-complet et non pas comme un problème NP-difficile ? La page anglaise elle-même parle de "NP-hard" pour Max-Clique.

Exemple de source : http://www.cc.gatech.edu/~mihail/D.7520reading/7520arorastocsurvey.pdf

En fait le problème d'optimisation (trouver la clique max) est NP-difficile (dans ce contexte NP-complet n'a pas de sens), et le problème de décision associé est NP-complet. J'ai corrigé rapidement. Merci pour la remarque ! --Roll-Morton (discuter) 11 juillet 2014 à 10:07 (CEST)

Ca n'a de sens de parler de NP-dureté, NP-complétude que pour un problème de DECISION. Fschwarzentruber (discuter) 20 mai 2016 à 20:50 (CEST).