Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Classe d'isomorphisme (théorie des graphes)

Posté par
tomsoyer
08-12-19 à 00:11

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

Posté par
carpediem
re : Classe d'isomorphisme (théorie des graphes) 08-12-19 à 00:15

salut

qu'est-ce qu'un graphe ?

Posté par
tomsoyer
re : Classe d'isomorphisme (théorie des graphes) 08-12-19 à 00:23

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 P_2(S). 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.

Classe d\'isomorphisme (théorie des graphes)

Posté par
Ulmiere
re : Classe d'isomorphisme (théorie des graphes) 08-12-19 à 01:58

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'

Posté par
carpediem
re : Classe d'isomorphisme (théorie des graphes) 08-12-19 à 09:44

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é ...

Posté par
jarod128
re : Classe d'isomorphisme (théorie des graphes) 08-12-19 à 09:59

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...

Posté par
jarod128
re : Classe d'isomorphisme (théorie des graphes) 08-12-19 à 11:20

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 ?

Posté par
tomsoyer
re : Classe d'isomorphisme (théorie des graphes) 08-12-19 à 17:25

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.

Posté par
jarod128
re : Classe d'isomorphisme (théorie des graphes) 08-12-19 à 17:36

Ton erreur est les deux classes où un seul point est isolé.  En effet si un seul point est isolé alors les deux autres sont reliés, une seule classe donc.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !