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

Prouver que 2 graphes ne sont pas isomorphes

Posté par
random
11-11-20 à 13:21

Salut !

Cela fait un moment que j'essaye de montrer si ces deux graphes sont isomorphes ou pas, j'ai essayé toutes les bijections possibles mais aucune ne semble fonctionner, donc je suis à peu près sûre qu'ils ne sont pas isomorphes, mais comment le prouver? Je sais que la méthode consiste à trouver une propriété que l'un des graphes possède mais pas l'autre, pourtant mes deux graphes ont le même nombre de sommets avec le même degré, et sont connectés (mais pas de la même manière). Je suis un peu perdu à ce stade.

Prouver que 2 graphes ne sont pas isomorphes

Posté par
jarod128
re : Prouver que 2 graphes ne sont pas isomorphes 11-11-20 à 13:41

Bonjour, dans le graphe de droite on trouve facilement des sous-graphes à 4 sommets connexes (en sablier) alors qu'il n'y en a pas dans celui de gauche.

Posté par
carpediem
re : Prouver que 2 graphes ne sont pas isomorphes 11-11-20 à 13:43

salut

il me semble qu'en déformant le pentagone intérieur du second on peut se ramener au pentagone étoilé du premier ...

d'autre part il peut être judicieux de numéroter 1 2 3 4 5 les sommets des deux "grands pentagones et a  b  c  d  et e celui des petits pentagones ...

Posté par
jarod128
re : Prouver que 2 graphes ne sont pas isomorphes 11-11-20 à 13:44

je voulais parler de sous-graphes à 4 sommets connexes eulériens

Posté par
random
re : Prouver que 2 graphes ne sont pas isomorphes 11-11-20 à 13:59

jarod128jarod128
  
Bien jouer ! Ca m'avait echapper. Donc est-il suffisant que je dise: 'Le graphe de droite contient plusieurs sous-graphes à 4 sommets connexes eulériens, ce qui n'est pas le cas pour le graphe de gauche ou doit-je aussi justifier pourquoi le graphe de gauche n'en contient pas ?

Posté par
jarod128
re : Prouver que 2 graphes ne sont pas isomorphes 11-11-20 à 14:04

Si tu as vu la notion de diamètre, celui de gauche est de 2 alors que celui de droite est 3 me semble-t-il.

Posté par
Maru0
re : Prouver que 2 graphes ne sont pas isomorphes 11-11-20 à 14:37

J'interviens pour donner une méthode en plus : le graphe de gauche n'est pas hamiltonien (c'est le graphe de Petersen) alors que celui de droite l'est

Posté par
random
re : Prouver que 2 graphes ne sont pas isomorphes 11-11-20 à 18:56

Merci Maru0 !



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 1674 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 !