Morphisme d'un graphe
Bonjour,
Je suis pas un matheux pour 2 ronds mais j'ai une question sans doute naîve pour le connaisseur qui est la suivante:
1. Si je prends n points (sur une feuille de papier ou dans l'espace) peu importe. Combien de graphe réellement différent je peux former avec ces n points?
Qu'est-ce que j'entend par " Réellement différent":
G(i) et G(j) sont 2 graphes de mon groupe recherché si il n'existe aucune symétrie possible reliant G(i) à G(j) et ça pour tout G(i) et G(j) de mon groupe.
Bref, les graphes de mon groupe ont tous des "topologie" "morphismes" différents. Je ne sais pas quel est le bon terme...j'espère que les matheux verront ce que je veux dire....
Merci par avance de vos réponse ou éclaircissements...
Je suis pas un matheux pour 2 ronds mais j'ai une question sans doute naîve pour le connaisseur qui est la suivante:
1. Si je prends n points (sur une feuille de papier ou dans l'espace) peu importe. Combien de graphe réellement différent je peux former avec ces n points?
Qu'est-ce que j'entend par " Réellement différent":
G(i) et G(j) sont 2 graphes de mon groupe recherché si il n'existe aucune symétrie possible reliant G(i) à G(j) et ça pour tout G(i) et G(j) de mon groupe.
Bref, les graphes de mon groupe ont tous des "topologie" "morphismes" différents. Je ne sais pas quel est le bon terme...j'espère que les matheux verront ce que je veux dire....
Merci par avance de vos réponse ou éclaircissements...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
D'abord sur la nature de tes graphes :
1°) Sont-ils orientés ?
2°) Peut-on avoir plusieurs arêtes entre deux sommets ?
3°) Peut-on avoir une arête dont les deux extrémités sont le même sommet ?
Ensuite sur ce que tu appelles "symétrie".
Soit $G_i=(S_i,A_i)$ deux graphes ($i=1,2$), où $S_i$ est l'ensemble des sommets et $A_i$ l'ensemble des arêtes.
Est-ce que pour toi, une symétrie c'est :
une bijection $\sigma : S_1\to S_2$ et une bijection $\alpha : A_1\to A_2$ (bijection, ça va, ou je dois expliquer ?) telles que pour toute arête $a\in A_1$ d'extrémités $s$ et $t$, l'arête $\alpha(a)\in A_2$ a pour extrémités $\sigma(s)$ et $\sigma(t)$ ?
1°) Sont-ils orientés ? Non
2°) Peut-on avoir plusieurs arêtes entre deux sommets ? non, 1 seule arête.
3°) Peut-on avoir une arête dont les deux extrémités sont le même sommet ? non
Ensuite sur ce que tu appelles "symétrie".
Symétrie:
Si dans un triangle, je permute A,B,C en B,C,A, j'ai toujours un triangle. On peut parler de permutation. Mais j'ai toujours au final un triangle.
ça permet de t'éclaircir un peu? Merci
@Vegadebaran
1)Deux graphes "symétriques" au sens où tu l'entends ont- ils forcément le même nombre d'arêtes?
2)Considères-tu que parmi les graphes à trois sommets A, B ,C, le graphe qui n'a que l'arête AB est "symétrique" du graphe qui n'a que l'arête BC?
Oui, à ta question sur la symétrie. je regarde attentivement ton lien et t'en remercie vivement.
A pdepasse:
Merci pour l'intérêt que tu portes à cette question.
Je vais essayer de répondre au mieux:
1) Oui. Mais ils n'ont pas nécessairement la même matrice d'adjacence
2) Oui. Mais j'impose que tous les sommets doivent avoir au moins 1 connexion. Pour un graphe à 3 sommets, les possibilités sont simples:
a. le triangle
b. la ligne constituée de 3 points
Si je ne fais pas d'abus de langage: Toutes les permutations de la ligne et du triangle sont des symétries donc "ne comptent pas" selon mon propos.
C'est facile à dénombrer "à la main" pour 3, 4 ou 5 points. Mais ça devient extrêmement complexe (pour moi) passé la dizaine.
Après réflexion, si on représente un graphe par sa matrice d'adjacence, alors 2 graphes A, B sont "différents" (selon ma ""définition""), si il n'existe pas de matrice de permutation permettant de passer de la matrice représentant le graphe A vers la matrice représentant le graphe B.
Enfin, j'espère que c'est à peu prêt vaguement clair
Est-ce à peu prêt ça (??)
La formule du lien que tu m'as remis est assez complexe. Mais à la première vue des résultats, ça a l'air d'être ça.
Je te remercie beaucoup.
Si tu ajoutes des conditions (non standard) en cours de route, ça va être difficile. Ce qui est fait de façon standard c'est soit d'énumérer les graphes sans condition de connexité (ce qui est fait dans le lien que j'ai donné), soit d'énumérer les graphes connexes (ce qui est fait en A001349 - OEIS).
Pourquoi imposes-tu cette condition et pas la connexité du graphe ?
Enfin, si tu veux vraiment la condition que tu indiques (le degré de chaque sommet est supérieur ou égal à 1), tu prends la suite a(n) de A000088, et ce que tu cherches est donné par b(n)=a(n)-a(n-1).
@Vegadebaran
Le mot "symétrique", à lui tout seul, NE VEUT RIEN DIRE. On définit une "relation symétrique", on définit le "symétrique d'un point par rapport à un autre", on appelle "groupe symétrique" un groupe de permutations, mais nulle part tu ne trouveras de définition mathématique du mot "symétrique".
N'empêche que souvent ON a bien envie de dire de deux trucs dont ON trouve qu'ils se ressemblent qu'ils sont "symétriques". Le problème est que ON est souvent tout seul à penser à cette "symétrie" et si ON veut se faire comprendre par d'autres ON doit DEFINIR PRECISEMENTce que l'ON appelle "symétrique"!
Cordialement
Oui merci de rappeler ce point. Je m'efforcerai de mieux faire la prochaine fois...
A Bu:
Merci à nouveau pour les formules. Je n'ajouterai plus de condition cette fois.
Mais nous ne sommes pas à la cours d'école.
Parmi nous il y a des gens passionnés qui dans la vie ont un travail et ne font pas des maths toutes la journée.
Ils ont 30, 40 50 60 ans.. Il y a des physiciens, des géologues, des retraités, des agriculteurs, des étudiants...
Alors, soyez un peu plus souples . Car vos "ON" et vos "DEFINIR PRECISEMENT' sont un peu déplacés...!
Si aussi des gens n'utilisent pas le vocabulaire approprié, soyez ouvert et compréhensifs. Et guidez les vers les bons choix sans donner l'impression de donner des coups de baguette..
Car à ce moment là, je vous invite dans un secteur qui ne serait pas votre spécialité, et vous verrez comment ça se passe...
Le fait de poser des questions sur ce forum est noble en soit.
Pensez-y..Merci beaucoup...Bien à vous.
Un amateur éclairé...
Pauvre Paul qui n'en n'a pas mérité autant !!:-)
Il avait pourtant raison, mais c'est vrai, c'est de l'histoire ancienne.
Cordialement,
Rescassol
Sauve qui peut
dire qu'elles étaient vertes les étoiles sur la la voiture rose.
Bien à toi
Paul