3 colorations, recherche de sous-graphes

Flo157
Flo157
dans Combinatoire et Graphes
Bonjour à tous. J'ai quelques petites notions de théories des graphes mais un peu moins d'algorithmique.

Ma question: existe-t-il un algorithme pour savoir si un graphe $G$ est contenu dans un graphe $G'$, en temps polynomial ?
(il me semble que le terme adapté est de dire que $G$ est un sous-graphe de $G'$)

J'ai envie de dire non, et je m'explique. J'ai remarqué qu'à un nombre de sommets donnés et à un jeu de 3 couleurs donné, il existe un graphe qui maximise le nombre d'arêtes.

Exemple, je prends 6 sommets, 3 rouges, 2 verts et 1 bleu. Je trace tous les liens possibles jusqu'à impossibilité (nécessité d'une quatrième couleur) et je m'arrête juste avant. J'appelle ce graphe maximal pour le jeu de 3 couleurs $(3,2,1)$
Et j'affirme que tout graphe 3-coloriable non biparti colorié de cette façon est sous-graphe du graphe maximal.

Or, il se trouve que l'on peut dénombrer les jeux de 3 couleurs via la décomposition d'un nombre entier $n$ en somme de trois nombres.
Cette décomposition se trouve en temps $O(n^{3})$.

Du coup, pour savoir si un graphe $G$ à $n$ sommets est 3-coloriable, il suffirait de déterminer les graphes maximaux en nombre d'arêtes (cela se fait certainement en $O(n^{k})$) et de savoir si le graphe $G$ est sous-graphe d'un des graphes maximaux (et non biparti).

Évidemment, cela nécessite que la question tout au dessus se fasse en temps polynomial et je me doute bien que cela a peu de chance d'être possible (puisque savoir si un coloriage en 3 couleurs est réalisable est np-complet), mais ça vaut le coup de demander
(je ne suis pas sûr de vraiment comprendre ces notions de complétudes).

Réponses

  • Næ
    Næ
    En admettant ce que tu affirmes sur la 3-coloriabilité et les sous-graphes de ton «graphe maximal», la réduction me semble marcher : tu pars bien d'une instance d'un problème de 3-coloriage, et la réduit polynomialement en le problème de sous-graphe que tu évoques. C'est quand même bien, pour éviter de tomber dans des pièges, d'expliciter en particulier la manière dont la taille de ce que tu manipules évolue (typiquement le «cela se fait certainement en $O(n^k)$» serait un peu plus rassurant si on avait une valeur fixée ne dépendant pas de $n$ à se mettre sous la main pour $k$ ; après pour ce coup là, j'ai effectivement bien envie de te faire confiance tout même ! ^^)

    Sinon, ici, une manière sûrement plus simple de voir que le problème consistant à décide si un graphe est sous-graphe d'un autre est difficile, c'est de voir que le problème de décision associé au problème de la clique (qui est un des problèmes assez fondamentaux en NP-complétude, en général un des premiers dont on montre la NP-complétude une fois que l'on a le théorème de Cook et alors 3-SAT qui est NP-complet), est en fait exactement un problème de sous-graphe (on cherche à déterminer si le graphe complet d'une certaine taille est un sous-graphe d'un graphe donné).
    C'est peut-être moins rigolo que de passer par 3-COLOR ceci-dit, c'est vrai ! :p
  • Flo157
    Flo157
    @Nae : Merci pour ta réponse! Je ne connaissais pas le problème de la clique, ni le théorème de Cook. Ce sont des problèmes très intéressants (notamment le fait que l'on peut utiliser SAT pour démontrer que pas mal de problèmes sont NP-complets).

    Concernant mon "certainement $O(n^{k})$" :
    Une fois tous les jeux de 3 couleurs déterminés: Je reprends l'exemple de $(3,2,1)$. Je prends un sommet rouge et je le relie à tous les sommets bleus et verts. Je fais ça pour les 3 sommets rouges. Puis je passe aux 2 sommets bleus, que j'ai juste à relier au sommet vert (car ils sont déjà reliés aux sommets rouges).
    Du coup, on peut généraliser. J'ai des nombres $(a_{1},...,a_{p})$ qui correspondent à un jeu de $p$ couleurs tels que $$\sum_{k=1}^{p}a_{k}=n$$ $n$ étant le nombre de sommets.
    Je commence par mes $a_{1}$ sommets coloriés avec la couleur 1.
    Je dois relier les à $a_{2}+a_{3}+\cdots+a_{p}=n-a_{1}$ sommets. J'ai donc $a_{1}(n-a_{1})$ opérations.
    Puis ensuite, je dois relier $a_{2}$ sommets à $a_{3}+\cdots+a_{p}=(n-a_{1}-a_{2})$ autres sommets. J'ai donc $a_{2}(n-a_{1}-a_{2})$ opérations.
    Je continue, et j’obtiens : $$
    \sum_{k=1}^{p} a_{k}(n-\sum_{i=1}^{k}a_{i})=\sum_{k=1}^{p} a_{k}n -\sum_{k=1}^{p}\sum_{i=1}^{k}a_{k}a_{i}=n^{2}-\ldots
    $$ Je pourrais m'arrêter là car on voit que la complexité est en $O(n^{2})$. Cependant,
    pour calculer $\ldots$, on fait quelques essais :
    pour $p=3$, on a : $\quad\displaystyle a_{1}^{2}+a_{1}a_{2}+a_{2}^{2}+a_{1}a_{3}+a_{2}a_{3}+a_{3}^{2}$
    Pour $p=4$, on a : $\quad\displaystyle a_{1}^{2}+a_{1}a_{2}+a_{2}^{2}+a_{1}a_{3}+a_{2}a_{3}+a_{3}^{2}+a_{1}a_{4}+a_{2}a_{4}+a_{3}a_{4}+a_{4}^{2}$

    La formule générale qu'on peut établir pour $\ldots$ est $$
    \frac{1}{2} \big((a_{1}+\cdots+a_{p})^{2}+(a_{1}^{2}+\cdots+a_{p}^{2}) \big)=\frac{1}{2}n^{2}+\frac{1}{2}\sum_{k=1}^{p} a_{k}^{2}
    $$ Et finalement le nombre exact d'arêtes à tracer est (en soustrayant $\ldots$) $$
    \frac{1}{2}n^{2}-\frac{1}{2}\sum_{k=1}^{p} a_{k}^{2}.
    $$ La complexité totale (pour ramener à un problème de sous-graphe) est donc $O(n^{5})$
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 3

GG +2 Invités