Quelqu'un se débrouille un peu en Théorie des graphes ici?

[Henley]

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.

[fatal_error]

salut,

pas trop essayé de comprendre la preuve (ni la construction/algorithme) mais:

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 ?

lun ou lautre

pour G+x cographe, soit M est vide, soit M\alpha...
si M est vide, alors G+x cographe
si M\alpha... alors G+x cographe

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?

je sais pas ce que tu appèles 2.2.
Il faut bien faire gaffe, l'auteur traite le cas Only if
Puis le cas If.

je rappèle (1), et (2) ((les deux cond du th))
(1) M vide
(2) M privé de alpha...

partie Only if: l'auteur s'intéresse au cas M non vide. Il démontre que (2) doit etre respecté sinon on a pas cographe

partie If:
"1. If M is empty": M vide. L'auteur montre qu'alors on peut construire un cographe
"2. There is a lowest". L'auteur montre que si (2) est vrai alors on peut construire un cographe

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

c'est les noeuds dans T (le cotree). C'est la même notation que dans wiki. le noeud 0 représente l'union disjointe entre les sous graphes "enfants" et le noeud 1 représente l'opération join), genre par ex sur Fig1. pour {{a,b},c} et {d,e,f} l'op join cree les arretes ad, ae, af, bd, be, bf, cd,ce,cf