Discussion :

[hajara]

Bonjour tout le monde
Etant donné un graphe connexe formé par un triangle et un paralélogramme ils ont une arrete en commun, je voulais faire un algo recursive qui a chaque fois supprime une arrete jusqu'a trouver un arbre pour avoir un arbre il faut que le graphe reste connexe parce que il ya possibilié que je supprime une arrete qui me deconnecte mon graphe et le rend non connexe (c ad deux sous graphe qui ne sont pas relié).
les test d'arret de mon algo sont non connexe et arbre.
Pour arbre voila il faut que [(le nombre de sommets -1)=(nombre des arretes)
et pour connexe ou non connexe je sais pas comment faire
SVP comment je peux savoir la caractérisation de la connexité du graphe

Merciii de m'aider

[Invité]

slt,

SVP comment je peux savoir la caractérisation de la connexité du graphe

Plusieurs possibilités, dont:
- tu peux faire un parcours de graphe en largeur/longueur et stocker tous les noeuds dans une liste, et comparer cette liste avec la liste de tous les noeuds. Si c'est la même, ton graphe est connexe, sinon c'est que tu as pas un graphe connexe.

- tu peux créer une matrice d'adjacence de ton graphe, lorsque tu retires une arretes, tu retires un 1 dans ta matrice. Tu as qu'à chercher les chemins de longueur k pour k=1 à n (idem prendre S=M+M^1+...+M^n) où M est ta matrice d'adjacence, n ton nombre de noeuds. Si S est remplie que de 1, ca veut dire que tous tes noeuds sont reliés et donc que ton graphe est connexe

[davcha]

Tu as la matrice d'adjacence A de ton graphe, A_{ij} = 1 s'il existe une arête entre les noeuds i et j, 0 sinon.

Tu calcules le nullspace du laplacien L de A ; L = D - A, avec D la matrice diagonale avec les entrées (d_1,...,d_n), où d_i est le degré du noeud i (le nombre d'arêtes incidentes au noeud i).

Si le rang du nullspace en question est d'ordre 1, alors tu es connexe. Si c'est supérieur à 1, alors tu n'es pas connexe.

[hajara]

Je vais essayer avec vos suggestions,
merciii beaucoup pour votre aide