Le nombre de sous-graphes connectés (!) Est exponentiel?

Question

Je veux montrer que pour un exemple de famille de graphes, le numbre des sous-graphes connectés croît expnential avec n.

facile à montrer un graphique complet, car un graphe complet a

n (n-1)/2 = n sur 2

bords. Un bord est soit dans le sous-graphe ou non. Par conséquent, chaque sous-graphe, peuvent être quantifiées avec un nombre binaire de la longueur

2^(n sur 2)

et parce que son graphe complet, chaque sous-graphe est connecté. Mais supposons, par exemple, que nous voulions montrer que le nombre de sous-graphes connectés dans un graphe à 3 ou 4 points croît aussi de manière exponentielle. Nous pouvons énumérer les sous-graphes de la même manière. Mais nous devons exclure beaucoup d'entre eux, car ils ne sont pas connectés.

Comment pouvons-nous faire cela? Existe-t-il un moyen de distinguer tous les sous-graphes connectés des non connectés?

Salutations et merci pour vos pensées

Answer 1

Cette idée est facile de prouver pour certaines familles de graphiques, et en particulier les familles des graphiques avec un haut « Edge-connectivité » (voir https://en.wikipedia.org/wiki/K-edge-connected_graph). Pour une connectivité de périphérie supérieure à k, vous pouvez toujours choisir k sommets à supprimer et générer un graphe connexe. Par conséquent, vous obtenez au moins des graphes Summation (j = 1 .. k; E-choose-k) où E est le nombre total d'arêtes. Soit k> (E/m) pour une constante m.

Alors en effet, le nombre de sous-graphes augmentera de façon exponentielle.