Inscription / Connexion Nouveau Sujet
Graphe connexe ou complet ?
Bonjour,
Voila, j'ai Bac Blanc demain et je révise mes cours de spécialité.
Or, j'ai un gros souci : quelle est la différence entre un graphe connexe et un graphe complet ?
En effet, un graphe connexe est défini comme un graphe où existe une chaîne entre deux sommets quelconques de ce graphe.
Un graphe complet est un graphe où deux sommets quelconques sont reliés par une arête.
Enfin bref, je comprends pas trop la différence...
Si vous pouvez m'aider, Merci vraiment !
salut
il suffit de lire la définition
G est complet :: quels que soient les sommets A et B il existe une arête reliant A et B
G est connexe :: quels que soient les sommets A et B il existe un chemin de sommets reliés par des arêtes allant de A à B
....
Un graphe complet est donc un graphe connexe particulier en fait ?
En fait, du moment que le graphe n'est pas "séparé en deux" il est forcément connexe je présume ?
Un graphe qui ressemblerait à
A---B C---D
Ne serait pas connexe alors qu'un A--B-C---D le serait, c'est ca ?
oui en gros c'est çà.
S'il y a des parties "isolées" le graphe n'est pas connexe.
et oui, un graphe complet est un graphe connexe.
(et c'est donc faux dans l'autre sens, avec les exemples vus plus haut)
Carpdiem : 
Bon une piste: par récurrence :
A chaque fois que tu rajoutes un sommet, il faut le relier aux (n-1) sommets déjà présents..
Donc si X(n) est le nombre d'arrete avec n sommets, tu as:
X(n)=X(n-1)+(n-1)
et comme X(1)=0
ou X(2)=1 come tu ^preferes, tu en deduis X(n) facilement....
BOn couarge
Annuler
connectez vous