déconnecter un graphe
Bonjour
Je suis béotien un théorie des graphes et je sèche sur l'exercice suivant. Soit $G$ un graphe planaire à $n$ sommets et $k$ arêtes.
On appelle connectivité de $G$ (et on note $c(G)$) le plus petit nombre de sommets à ôter à $G$ pour que $G$ ne soit pas connexe.
Montrer que $c(G)\leq \frac{2k}{n}$.
Je sèche complètement, je ne vois pas du tout d'où ça vient, n'ai pas l'embryon d'une piste. La seule chose que je vois c'est que si $2k<n$ (et donc $\frac{2k}{n}<1$) le graphe n'est effectivement pas connexe et on a bien $c(G)=0$.
Toute aide est la bien venue.
Merci.
Je suis béotien un théorie des graphes et je sèche sur l'exercice suivant. Soit $G$ un graphe planaire à $n$ sommets et $k$ arêtes.
On appelle connectivité de $G$ (et on note $c(G)$) le plus petit nombre de sommets à ôter à $G$ pour que $G$ ne soit pas connexe.
Montrer que $c(G)\leq \frac{2k}{n}$.
Je sèche complètement, je ne vois pas du tout d'où ça vient, n'ai pas l'embryon d'une piste. La seule chose que je vois c'est que si $2k<n$ (et donc $\frac{2k}{n}<1$) le graphe n'est effectivement pas connexe et on a bien $c(G)=0$.
Toute aide est la bien venue.
Merci.
Réponses
-
Si $k<n-1$, le graphe ne peut pas être connexe (et c'est optimal, un arbre - connexe - a $n-1$ arêtes).
-
Merci pour ta réponse, GaBuZoMeu, mais je ne vois pas du tout comment l'utiliser...
-
Je ne pense pas que ça serve. C'était juste que ton $k<n/2$ n'était pas optimal.
PS. Dans un graphe à $n$ sommets et $k$ arêtes, le degré minimum d'un sommet est au plus égal à $2k/n$. -
Ok. Je savais que mon inégalité n'était pas optimale, c'était juste pour dire que dans le cas ou $\frac{2k}{n}<1$, on a bien $c(G)=0$.
Je vais maintenant réfléchir à ton PS, qui me semble une piste intéressante !
Encore merci ! -
Il doit y avoir des conditions sur $n$ et la condition de planarité me paraît inutilement forte. Parce que si $n \leq 4$ et que $G=K_n$ (graphe complet), il est impossible de perdre la connexité en enlevant des sommets. Donc, on va supposer que $n \geq 5$ et du coup, puisque le graphe est planaire, ce n'est pas un graphe complet et $k < \frac{n(n-1)}{2}$, d'où $\frac{2k}{n} < n-1$.
La somme des degrés étant le double du nombre d'arêtes vaut donc ici $2k$.
Ainsi, le degré moyen dans le graphe est $\frac{2k}{n}$. En particulier, il existe un sommet de degré $d \leq \frac{2k}{n}$. Si on élimine tous ses voisins, ce sommet est alors isolé (on a éliminé au plus $n-2$ sommets, donc il en reste au moins deux) et le graphe résultant n'est plus connexe.
Cela dit, du moment qu'au départ $G$ n'est pas complet, planaire ou pas, ça marche.
Pierre. -
PierreB, tu n'as pas laissé le loisir à gimax de conclure son exercice lui-même avec l'indication que je lui avais donnée.
Il convient bien sûr de mettre à part les graphes complets qu'il est impossible de déconnecter en supprimant des sommets. -
Je reviens tardivement pour vous remercier. J'étais sans internet depuis une dizaine de jours.
Merci à tous les deux.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres