Bonjour,

voilà je dois expliquer "dans les grandes lignes" cet algorithme qui reconnaît les co-graphes, il se trouve page 5 (au cas-où : "Un cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud.")
donc j'ai réussi à avancer un peu cependant quelques questions résident

PDF : https://www.docdroid.net/oiCcL0L/docume ... toires.pdf



1) à la page 4 dans le "Théorème 1" quand on nous donne les conditions pour que G+x soit reconnu comme cographes
il faut que 1. ET 2. soient vrais ? ou juste l'un des 2 ?

2) dans l'algorithme (retour page 5 donc), au 2.2, on traite là le cas le plus trivial en premier c'est bien ça ? est-ce que ce cas équivaut au "1." des 2 conditions énumérées dans le "Théorème 1" donc j'ai parlé juste au-dessus?

3) que signifie les "(1) nodes" ou "(0) nodes dont ils parlent ? je n'ai pas bien saisi cette notation du coup ça me désoriente un peu

ou si tout simplement vous comprenez l'algorithme dans sa généralité sans trop de problème et que vous pouvez m'expliquez un peu comment il fonctionne je ne crache pas dessus non-plus mais sinon ce n'est pas grave si vous avez une réponse à une de mes questions cela me débloquera déjà beaucoup et je vous en remercie.

Salut,

Vous vous y prenez un peu tard.

Juste rapidement, sans trop réfléchir :

1. Il faut et il suffit que l'une des deux propositions soient vraies ("M is empty or M{a} consists ..."). Par contre, pour que 2) soit vraie, il faut vérifier à la fois (i) et (ii).

2. Pas le temps de me plonger dans l'algo. Que fait l'algo MARK et à quoi correspond le fait que tous les éléments aient été marqués puis démarqués ? A priori vu qu'on fini l'algo dans ce cas, ça correspond effectivement à un cas simple, mais il faudrait que je lise le papier pour être sûr.

3. Page 2, les nœuds de l'arbre sont labellisés 0 ou 1 en fonction de la parité de leur profondeur, regarde l'arbre de la figure 1 pour voir à quoi ça correspond. Les (1) nodes sont donc les noeuds de label 1.

-
Edité par melepe 3 mai 2018 à 11:50:21

ah putain mdrrrrrrrrrrrrrrr on voit le "à rendre pour le 6 mai" à droite hahahahahahahahahahaha bien vu (en fait je suis passé par une sacré merde ce semestre j'ai jamais vu ça, donc j'avais pas eu le temps d'y toucher, mais j'aurais dû m'organiser)

ok c'est bien ce que je pensais pour le 1.

oui ça roule justement j'ai planché dessus j'ai fini par comprendre un peu mieux ! merci beaucoup pour votre réponse en tout cas !

sinon au cas où : alors dans mes notes j'ai écrit cela :

Pour chacun de ces nœuds, on lancera la procédure de marquage qui marque toutes les feuilles adjacentes à x. (pour cela il itère tous les sommets de T)

Puis, on vérifie d’abord l’égalité d(u) = md(u) pour savoir les nœuds à démarquer. Pour chaque nœud u de T qui ont tous leurs enfants qui ont été marqués ou démarqués (d(u) = md(u)), on démarque u.

Et si u n’est pas la racine on marque le parent de u.

je pense que c'est bon normalement

-
Edité par henleybidon 4 mai 2018 à 0:40:41