Chapitre 12 • Intro duc tion à l’aide multi cri tère à la déci sion
434
– deux som mets quel conques d’un noyau ne peuvent pas être adja cents :
4a P N, 4b P N, non(aSb) et non(bSa)
– pour tout som met hors du noyau, il existe un arc depuis un som met du noyau vers
ce som met :
4b x N Ea P N : a Sb
Un noyau est donc un sous ensemble d’actions incom pa rables tel que toute action
ne fai sant pas par tie du noyau est sur clas sée par au moins une action du noyau.
Tout graphe sans cir cuit admet un noyau unique. Un graphe avec cir cuit peut
admettre aucun, un ou plu sieurs noyaux.
L’algo rithme sui vant per met de détecter le noyau d’un graphe G sans cir cuit.
(0) Repré sen ter G par son « dic tion naire des pré cé dents » (ce dic tion naire asso cie à
chaque som met la liste de ses pré cé dents ou « prédécesseurs »)
Tant que pos sible faire
(1) Mar quer tout som met dont la liste est vide (sans prédécesseurs)
(2) Bar rer tout som met qui contient au moins un som met mar qué dans sa liste
(3) Sup pri mer des listes les som mets bar rés
L’ensemble des som mets mar qués à l’issue de l’algo rithme consti tue le noyau.
Lorsque le graphe contient des cir cuits, on peut, par exemple, réduire les cir
cuits (c’est àdire contrac ter en un som met unique tous les som mets fai sant par
tie d’un même cir cuit et pré ser ver les arcs avec les som mets exté rieurs au cir cuit).
Cette opé ra tion de réduc tion revient à consi dé rer que les som mets d’un même cir cuit
sont indif fé rents. On peut alors déter mi ner le noyau sur le graphe réduit (qui, par
construc tion, ne contient pas de cir cuit).
En pra tique, il ne suf fit pas d’exé cu ter une fois l’ensemble de ce pro ces sus et de
prendre le noyau résul tant comme recom man da tion. Il convient de pro cé der à une
ana lyse de robus tesse consis tant à répé ter le pro ces sus en fai sant varier les para mètres
cri tiques du modèle (seuil de concor dance, poids, seuils de veto…). La recom man
da tion sera consti tuée des actions appa rais sant régu liè re ment dans le noyau.
Exemple 2 « Choix d’un loge ment » (fin)
L’appli ca tion de l’algo rithme de détec tion du noyau au graphe de sur clas se ment
de la figure 12.7 conduit au noyau (unique) N 5 5, 4 ,, 5 6. Afin d’esquis ser une ana
lyse de robus tesse, on peut envi sa ger de modi fier le seuil de concor dance. En fixant
ce seuil s à 0,6 on obtient un graphe de sur clas se ment beau coup plus riche. Le
lec teur véri fiera qu’après avoir réduit les cir cuits du graphe pré cé dent, on obtient
comme noyau de ce nou veau graphe l’ensemble N r 5 5, 3 ,, 4 6. Il semble donc que
le loge ment , 4 , qui reste présent dans cha cun des noyaux, consti tue un choix inté
res sant. (pour les trois critères choisis par le décideur) :
434
– deux som mets quel conques d’un noyau ne peuvent pas être adja cents :
4a P N, 4b P N, non(aSb) et non(bSa)
– pour tout som met hors du noyau, il existe un arc depuis un som met du noyau vers
ce som met :
4b x N Ea P N : a Sb
Un noyau est donc un sous ensemble d’actions incom pa rables tel que toute action
ne fai sant pas par tie du noyau est sur clas sée par au moins une action du noyau.
Tout graphe sans cir cuit admet un noyau unique. Un graphe avec cir cuit peut
admettre aucun, un ou plu sieurs noyaux.
L’algo rithme sui vant per met de détecter le noyau d’un graphe G sans cir cuit.
(0) Repré sen ter G par son « dic tion naire des pré cé dents » (ce dic tion naire asso cie à
chaque som met la liste de ses pré cé dents ou « prédécesseurs »)
Tant que pos sible faire
(1) Mar quer tout som met dont la liste est vide (sans prédécesseurs)
(2) Bar rer tout som met qui contient au moins un som met mar qué dans sa liste
(3) Sup pri mer des listes les som mets bar rés
L’ensemble des som mets mar qués à l’issue de l’algo rithme consti tue le noyau.
Lorsque le graphe contient des cir cuits, on peut, par exemple, réduire les cir
cuits (c’est àdire contrac ter en un som met unique tous les som mets fai sant par
tie d’un même cir cuit et pré ser ver les arcs avec les som mets exté rieurs au cir cuit).
Cette opé ra tion de réduc tion revient à consi dé rer que les som mets d’un même cir cuit
sont indif fé rents. On peut alors déter mi ner le noyau sur le graphe réduit (qui, par
construc tion, ne contient pas de cir cuit).
En pra tique, il ne suf fit pas d’exé cu ter une fois l’ensemble de ce pro ces sus et de
prendre le noyau résul tant comme recom man da tion. Il convient de pro cé der à une
ana lyse de robus tesse consis tant à répé ter le pro ces sus en fai sant varier les para mètres
cri tiques du modèle (seuil de concor dance, poids, seuils de veto…). La recom man
da tion sera consti tuée des actions appa rais sant régu liè re ment dans le noyau.
Exemple 2 « Choix d’un loge ment » (fin)
L’appli ca tion de l’algo rithme de détec tion du noyau au graphe de sur clas se ment
de la figure 12.7 conduit au noyau (unique) N 5 5, 4 ,, 5 6. Afin d’esquis ser une ana
lyse de robus tesse, on peut envi sa ger de modi fier le seuil de concor dance. En fixant
ce seuil s à 0,6 on obtient un graphe de sur clas se ment beau coup plus riche. Le
lec teur véri fiera qu’après avoir réduit les cir cuits du graphe pré cé dent, on obtient
comme noyau de ce nou veau graphe l’ensemble N r 5 5, 3 ,, 4 6. Il semble donc que
le loge ment , 4 , qui reste présent dans cha cun des noyaux, consti tue un choix inté
res sant. (pour les trois critères choisis par le décideur) :