Bonjour, bonsoir,
Dans mes exercices, un exo me présente quelque difficulté
Combien y a-t-il, à isomorphisme près, de graphes d'ordre n, pour 1 ≤ n ≤ 4 ?
Malheureusement, je ne tombe pas en accord avec la correction. En effet, je considère qu'il y a respectivement 1,2,4 et 8 classe d'isomorphisme.
La correction indique : "respectivement 1, 2, 3, et 11 classes d'isomorphisme."
Quand pensez vous ?
Merci pour votre aide
Salut carpediem,
Un graphe (simple non-orienté, j'aurais du préciser) est un couple G=(S,A), où S est un ensemble fini quelconque et A un sous ensemble de . Les éléments de S sont appelés sommets et les éléments de A sont appelés arêtes.
Par exemple, voir l'image jointe.
Pour n = 1, un seule graphe, sans arête
Pour n = 2, celui où chaque point est isolé, et celui où ils sont reliés
Pour n = 3, il y a :
- celui où chaque point est isolé
- les deux classes où un seul point est isolé. Mais attention, on a dejà compté l'une des deux classes !
- la classe où aucun point n'est isolé
Ça fait bien trois.
Pour n = 4 :
- aucun point n'est isolé : il y a
1,2;3,4
1,2;2,3;3,4
1,2;2,3;3,4;1,4
1,2;1,3;3,4
1,2;1,3;2,4
1,2;1,3;1,4
- celui où chaque point est isolé (1 graphe)
- celui où trois points sont isolés : c'est le meme cas que celui où les 4 sont isolés
- cas où 2 points sont isolés. Il en reste deux à relier : 1 graphe
- cas où un seul point est isolé. Il y a 1,2;1,3;2,3
1,2;2,3
1,3;1,2
Ça fait onze
Faut vérifier les combinaisons, il est deux heures du mat'
merci tomsoyer : je sais ce qu'est un graphe et la question était pour toi : que tu saches ce que sais et que tu apportes les précisions nécessaires ...
et aussi préciser la notation P2(S) qui à nouveau est introduite sans être définie
pour te dire que tu comptes deux fois (ou plus) une même classe ... mais Ulmiere m'a devancé ...
Bonjour,
Il me semble que Ulmiere en a une de trop pour 1 seul point isolé mais qu'il lui en manque une pour aucun point isolé. D'où le bon total...
Je ne sais pas si on peut continuer ici ou aller en détente pour se poser la question d'une formule générale repondant au problème de départ ?
Merci infiniment à vous 3 pour toutes vos précisions.
Pour n=3 :
- celui où chaque point est isolé
- les deux classes où un seul point est isolé.
- la classe où aucun point n'est isolé : 1,2 ; 2,3. n'y a-t-il pas aussi 1,2 ; 2,3 ; 3,1?
Cela ferai 4 ?
Quoiqu'il en soit merci beaucoup, cela me parait beaucoup plus clair maintenant.
carpediem : tu as raison j'introduirai plus mes notations les prochaines fois.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :