Inscription / Connexion Nouveau Sujet
Niveau Licence Maths 1e ann
Partager :

Graphe sans point d'articulation

Posté par
MrocduPython
03-09-23 à 18:50

Bonjour.

Je considère un graphe simple non orienté, supposé connexe et sans point d'articulation. On note n le nombre de sommets, et p le nombre d'arêtes, et on suppose n 3.

Pourriez m'indiquer si les trois propriétés suivantes sont vraies? Connaissez un bonne référence sur ce sujet? Je vous remercie d'avance!

1) p n
2) p=n si, et seulement si, le graphe est un cycle
3) p=n+1 ssi le graphe est un cycle auquel on adjoint une chaine reliant deux de ses sommets.

Posté par
malou Webmaster
re : Graphe sans point d'articulation 03-09-23 à 19:44

Bonjour, bienvenue

Et si nous te demandons ce que toi tu en penses, tu réponds quoi ?

Posté par
MrocduPython
re : Graphe sans point d'articulation 03-09-23 à 20:55

Ce sont trois conjectures personnelles.
J'arrive à prouver 1) et 2), mais j'ai peur d'avoir fait des erreurs.
Et j'ai un doute sur 3).
J'aimerais beaucoup avoir des références sur le sujet, merci d'avance!

Posté par
carpediem
re : Graphe sans point d'articulation 04-09-23 à 09:17

salut

qu'est-ce qu'un point d'articulation d'un graphe ?

Posté par
MrocduPython
re : Graphe sans point d'articulation 06-09-23 à 17:00

Un point d'articulation est un sommet tel que, si on le supprime du graphe, le graphe n'est plus connexe.

Posté par
carpediem
re : Graphe sans point d'articulation 06-09-23 à 17:30

as-tu fait un dessin ? en particulier dans les cas 2/ et 3/ qui sont simples

je dirai que les trois sont vraies ...



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