Composantes connexes d'un graphe.

[invite12f9a090]

Bonjour,

J'étudie en ce moment la théorie des graphes et j'ai du mal a bien comprendre ce qu'est une composante connexe d'un graphe. Mon livre dit:

"Ce sont les sous-graphes engendrés connexes maximaux de G. Maximal signifie que le sous-graphe en question n'est pas lui même sous-graphe propre, c'est à dire ayant strictement moins de sommets, d'un sous-graphe connexe de G."

Il y a comme quelque chose qui bloque si vous voyez ce que je veux dire...
J'essais de me le représenter graphiquement mais je n'y parviens pas.

Merci beaucoup.
Bonne journée.
-----

[invite79d10163]

"Ce sont les sous-graphes engendrés connexes maximaux de G. Maximal signifie que le sous-graphe en question n'est pas lui même sous-graphe propre, c'est à dire ayant strictement moins de sommets, d'un sous-graphe connexe de G."

Bonjour,

Si le graphe est connexe, le graphe ne possède qu'une seule composante connexe, lui même. une composante connexe d'un graphe n'a donc pas strictement moins de sommets que le graphe lui même.

[invite12f9a090]

Merci pour votre réponse.

Un graphe G non connexe peut il avoir une (ou plusieurs) composante connexe qui est (me semble t-il) une partie de G connexe?

[Médiat]

Bonjour,

une composante connexe d'un graphe n'a donc pas strictement moins de sommets que le graphe lui même.

Je ne vois pas pourquoi, il suffit de prendre le graphe a 2 sommets et sans aucune arête, qui possèede deux composantes connexes n'ayant qu'un seul sommet.

Peut-être vouliez-vous dire :

une composante connexe d'un graphe connexe n'a donc pas strictement moins de sommets que le graphe lui même.

[A voir en vidéo sur Futura]

[invite14e03d2a]

Salut,

Je suppose qu'un graphe n'a qu'un autre fini de sommets, est orienté et qu'entre deux sommets, il y a au plus une arrête. Il y a pas mal de définitions différentes pour les graphes, dis-moi si ce n'est pas celle-ci que tu utilises.

Un graphe (comme défini ci-dessus) peut toujours être réalisé dans (pour n assez grand). On dira que le graphe est connexe si sa réalisation est connexe (au sens usuelle de la topologie).

Autre formulation, plus combinatoire: on dit qu'un graphe est connexe si toute paire de sommets peut être reliée par un chemin.

Cordialement

[invite79d10163]

Bonjour,

Je ne vois pas pourquoi, il suffit de prendre le graphe a 2 sommets et sans aucune arête, qui possèede deux composantes connexes n'ayant qu'un seul sommet.

Peut-être vouliez-vous dire :

Je voulais dire, qu'une composante connexe n'a pas toujours strictement moins de sommets que le graphe lui même. Autant pour moi.

[Médiat]

Un graphe G non connexe peut il avoir une (ou plusieurs) composante connexe qui est (me semble t-il) une partie de G connexe?

Un graphe non connexe possèede au moins deux composantes connexes, qui sont des parties connexes

[invite986312212]

les composantes connexes d'un graphe c'est tout bêtement les morceaux du graphe non reliés les uns aux autres par des arêtes. En théorie des graphes on n'étudie pas de but en blanc un graphe non connexe, ça n'aurait pas d'intérêt. Par contre quand on considère un sous-graphe ou un graphe partiel, il peut être non connexe (par exemple dans les problèmes de coloration, le sous-graphe partiel formé par les arêtes d'une certaine couleur peut être non connexe).