aide à la terminologie des sous-graphes

Question

Y at-il un terme pour décrire un graphique qui n'a qu'un seul sous-graphe qui est fortement liée? (Je ne suis même pas sûr que j'utilise fortement connecté correctement ici).

par ex. {AB, BC} a seulement un sous-graphe et {AB, BC, DE} en a deux.

Notez que je ne suis pas considérer que le graphique {AB, BC} a trois: {AB sous-graphes, BC} et {AB} et {BC}.

s'il vous plaît la distinction entre undirected et réalisé le cas échéant.

Answer 1

Je pense que vous voulez dire un graphique connecté, l'alternative étant un graphe déconnecté forêt .

De http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 -

Un graphe est appelé connecté si chaque paire de sommets distincts dans le graphique peut être connecté par un certain chemin. Un graphe orienté est appelé faiblement connecté si le remplacement de tous ses arêtes dirigées par des arêtes non orientées produit un graphe connecté (non orienté). Il est connecté s'il contient un chemin dirigé de u vers v ou un chemin dirigé de v vers u pour chaque paire de sommets u, v. Il est fortement connecté ou fort s'il contient un chemin dirigé de u à v et un chemin dirigé de v à u pour chaque paire de sommets u, v. Les composants forts sont les sous-graphes maximaux fortement connectés.