Bonjour à toutes et tous,

Je suis novice dans l'algorithmique des graphes et la réduction.Je fais face à 2 problèmes :

  1. Donnez un algo polynomial au problème 2-coloriable et justifier.

    Voici mon algo mais je sais pas s'il est valide et s'il est valide pourquoi on demande de justifier et c'est quoi la justification d'un algo polynomial pour 2-coloriable ?

    Soit G un graphe
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
pour tout sommet s € G :
     pour tout sommet t  € G différent de s :
         si t non adjacent à s 
              si t pas déjà coloré alors
                   colorer t avec la même couleur que s
               fin si
          sinon si t adjacent à s alors 
                colorer t avec la couleur opposée
       fin pour
fin pour


2ème problème : Montrer que le problème 4-coloriable est NP-complet.
Là j'ai aucune idée vraiment.

Merci d'avance pour vos aides.