Question sur les co-graphes !

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/document-decouverte-des-laboratoires.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.

Le Lui ou un Autre

Bonjour,

Les co-graphes ont une définition par construction et l'algorithme a pour but de retrouver cette construction, à isomorphisme près. Le co-arbre $T$ associé donne cette construction :
- $T$ est un arbre dont les feuilles correspondent aux sommets du co-graphe et dont les nœuds sont labellisés (0) ou (1). C'est à ça que fait référence les "(1) nodes" et les "(0) nodes".
- Pour chaque nœud $n$ de $T$ (qui n'est pas une feuille), considère un graphe $G_n$ dont les sommets sont les feuilles de $n$. Si le nœud $n$ est de type (0), $G_n$ est le graphe nul (sans arête), si le nœud $n$ est de type (1), c'est le graphe complet.

La construction du co-graphe se fait à partir des graphes $G_n$ en remontant l'arbre. Les arêtes entre les nœuds correspondent à l'opération d'union disjointe - si le nœud le plus haut dans l'arbre est de type (0) - ou bien à l'opération suivante sinon :
$$\complement(\complement G_{n1} \coprod \dots \coprod \complement G_{nk})$$

J'ai pris l'exemple de la figure 1 de l'article en faisant la construction pas-à-pas (clique sur l'image pour voir les étapes).

Le Théorème 1 indique que « $G$ est un co-graphe ssi 1. ou [ 2. (i) et 2. (ii) ] ».
Et donc les cas 2.2 et 2.3 de l'algorithme "Cograph-Recognition" correspondent bien aux cas les plus simples, où la construction de $G+x$ suit la construction de $G$ en rajoutant juste une opération ($\coprod$ ou le mix $\complement\coprod$ que j'ai écrit au-dessus).

J'espère que ça aide ;-)

Henley

wow absolument formidable merci ça m'éclaire bien ! je vais relire plusieurs fois pour comprendre mais ça me débloque beaucoup c'est super !
je reviendrais si j'ai des questions mais je vais essayer de me débrouiller !

merci encore !

Henley

dernière question juste :

tout à la fin en 2.5 on procède bien à la construction du co-graphe on est d'accord ?

Le Lui ou un Autre

Nous sommes d'accord et le paragraphe d'en-dessous est d'accord lui aussi.
D'ailleurs, tu remarqueras que la procédure de décision pour savoir si $G+x$ est un co-graphe est dans l'algorithme "Find-Lowest" (sauf le cas 1. du Théorème 1 qui est évacué avant). Si tu as un co-graphe $G$ avec son co-arbre $T$ et que le seul but est de déterminer si $G+x$ est un co-graphe, alors tu peux t'arrêter après le 2.4.

Henley

ahh super j'avais bien compris alors ! je voulais être bien sûr de ne pas avoir écrit n'importe quoi dans mon exposé, c'est bien comme ça que j'ai expliqué ça roule
c'est vraiment génial, je te remercie tu m'as été d'une grande aide !