Discussion :

[hamzawhy]

Bonjour,
soit G un graphe orienté d'ordre n ,qui contient un stable d'ordre n-1,est ce que les points d'articulation ou les isthmes existent pour ce type de graphe ou non.
et merci

[kwariz]

Bonsoir,

ce coup là je pense qu'il s'agit d'un exercice plus que d'un problème de compréhension.
Essayons de dessiner un graphe tel qu'il est donné : Un graphe G=(V,E) d'ordre n (a priori connexe ...) qui contient un stable d'ordre n-1. On note sans perte de généralité V={v₁, v₂, ..., vₙ₋₁, vₙ} avec S={v₁, v₂, ..., vₙ₋₁} le stable.

Le fait que S soit un stable que peux-tu en déduire ?
Existe-t-il des arêtes dont vₙ est un des sommets ?
Quel serait un dessin possible d'un tel graphe ?

[hamzawhy]

Bonsoir kwariz ce que j'ai compris à partir de ce que j'ai appris de notre cours de théorie des graphes,qu'un stable est un sous graphe sans arrêtes,et lorsqu'on parle d'un point d'articulation on parle d'un sommet dont la perte augmente la connexité de graphe,ma réponse était non pas de points d'articulation pour un tel graphe car la connexité ne va pas s'augmenté.

[hamzawhy]

Bon si on veut avoir un stable toutes les sommets sont tous isolés puisqu'il n'a pas d'arrêtes entre eux

[kwariz]

Oui c'est ça ... ça donne un dessin pour le stable comme :


Maintenant la question à se poser est : si on rajoute le sommet n quelles arête rajoute-t-on ? puis la question suivante est où sont les isthmes et où sont les points d'articulations ?

[hamzawhy]

voilà ma réponse et je suis désolé si j'ai commit une faute dans la réponse:
si on va ajouter une arrête reliant le sommet n avec l'un des sommets de graphe(par exemple le sommet1) on va avoir une chaine donc une composante connexe
mais la connexité ne s'augmente pas :/
toutes les sommets de graphe qui sont isolés sont des points d'articulation puisqu'il vont augmenter le nombre de connexité de graphe
l'isthme sera alors l'arrête qu'on a ajouté entre les 2 sommets.

[kwariz]

En fait c'est pas tout à fait ça ...
Tu sais au départ que tu as un graphe avec n sommets et au moins n-1 de ces sommets ne sont pas reliés deux à deux. Ce sous=graphe qui est le stable est celui que j'ai dessiné.
Il faut cependant ajouter encore un sommet pour retrouver le graphe de départ.

Soit on suppose que le graphe de départ est connexe et dans ce cas pour rendre connexe le stable et le sommet n connexe il faut que chaque sommet du stable soit relié au sommet n : le graphe est un graphe en étoile :

Je te laisse répondre à la question concernant l'existence ainsi que le nombre d'isthme et de points d'articulations.

Soit on suit l'énoncé à la lettre et on sait juste que le graphe contient un stable d'ordre n et on ne fait aucune supposition quant à sa connexité. Cela signifie qu'il existe entre 0 et n-1 reliant le sommet n à d'autres ... je te laisse faire les dessins et conclure sur l'existence et le nombre d'isthme et de points d'articulations.

Par de problèmes quant à ton orthographe

[hamzawhy]

merci kwariz pour l'aide

[kwariz]

L'important c'est que tu comprennes la démarche surtout
N'oublie pas de passer les sujet en résolus ... en utilisant le bouton

[hamzawhy]

Mr kwariz selon l’énoncé le graphe G est orienté,pendant le travail est ce que je suppose que le graphe est non orienté,en négligeant le sens des flèches?

[kwariz]

C'est une bonne question ... la bonne question est à quel moment ça va changer si on se place dans le cadre de graphes orientés ...

[hamzawhy]

je sais qu'un graphe orienté n'est qu'un cas spécifique d'un graphe non orienté

[kwariz]

Mais est-ce que quelque part dans la démonstration il y a quelque chose qui change si le graphe est orienté (selon tes connaissances et ton cours) ?

[hamzawhy]

non

[kwariz]

Si à aucun moment on ne peut identifier quelque chose qui ne serait pas valide en raisonnant avec des arcs ... c'est que c'est bon.