Théorie des graphes : 4 démonstrations ?
Bonsoir tout le monde,
J'étudie actuellement la théorie des graphes et j'aimerais m'avancer dans mon travail estudiantin Je fais donc appel à vous pour m'expliquer plusieurs démonstrations que je n'ai pas encore eu le temps de faire, bien entendu.
Voici donc lesdites démonstrations.
1. Montrez qu'un graphe simple a un nombre pair de sommets de degré impair. J'ai ma petite idée : je pense utiliser la formule "la somme des degrés d'un graphe = 2*card(ensemble des arêtes)" en séparant la somme des degrés de sommets à degrés impairs de la somme des degrés de sommets à degrés pairs… mais je ne vois pas trop comment.
2. Démontrez le Lemme de Koenig. Pour rappel, il dit qu'il existe nécessairement une chaîne élémentaire entre deux sommets s1 et s2 reliés par une chaîne quelconque. C'est tellement intuitif que c'en devient impossible à démontrer…
3. Démontrez que G connexe comporte au moins card(ensemble des sommets) - 1 arêtes.
4. Démontrez qu'il n'existe pas de graphe non-orienté ayant au moins deux sommets et tel que tous les sommets aient des degrés distincts.
Voilà. J'ai énormément de mal à savoir par où commencer les deux dernières démonstrations…
Merci d'avance et bonne continuation.
J'étudie actuellement la théorie des graphes et j'aimerais m'avancer dans mon travail estudiantin Je fais donc appel à vous pour m'expliquer plusieurs démonstrations que je n'ai pas encore eu le temps de faire, bien entendu.
Voici donc lesdites démonstrations.
1. Montrez qu'un graphe simple a un nombre pair de sommets de degré impair. J'ai ma petite idée : je pense utiliser la formule "la somme des degrés d'un graphe = 2*card(ensemble des arêtes)" en séparant la somme des degrés de sommets à degrés impairs de la somme des degrés de sommets à degrés pairs… mais je ne vois pas trop comment.
2. Démontrez le Lemme de Koenig. Pour rappel, il dit qu'il existe nécessairement une chaîne élémentaire entre deux sommets s1 et s2 reliés par une chaîne quelconque. C'est tellement intuitif que c'en devient impossible à démontrer…
3. Démontrez que G connexe comporte au moins card(ensemble des sommets) - 1 arêtes.
4. Démontrez qu'il n'existe pas de graphe non-orienté ayant au moins deux sommets et tel que tous les sommets aient des degrés distincts.
Voilà. J'ai énormément de mal à savoir par où commencer les deux dernières démonstrations…
Merci d'avance et bonne continuation.
Réponses
-
Figure toi, mon cher étudiant, que nous ne sommes pas là pour perdre notre temps au profit de ceux qui, eux, n'ont pas de temps à perdre pour réfléchir. C'est bien entendu?
-
J'ai énormément de mal à savoir par où commencer les deux dernières démonstrations…
Indications:
-pour la 3, chaque graphe connexe a la propriété qu'il existe au moins un sommet tel que si on l'enlève, on obtient encore un graphe connexe
-pour la 4, tu prends un sommet et regardes le graphe composé de l'ensemble de ses non voisins
pardonAide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Bonjour tout le monde,
Tout d'abord, merci d'avoir pris le temps de m'aider.
Je souhaite notamment répondre à depasse :
depasse écrivait : http://www.les-mathematiques.net/phorum/read.php?34,1007303,1007401#msg-1007401
En fait je ne suis pas censé faire ces démonstrations, j'essaie juste de prendre de l'avance. Bien entendu, et je pensais l'avoir montré notamment pour les deux premières démonstrations, j'ai réfléchi un minimum avant de créer ce topic.
Je comprends néanmoins ta réaction (quoique cette mode, cet état d'esprit, qui vise à "ne surtout pas fournir de réponses toutes-faites sur les forums" me laisse un petit peu perplexe tout de même, car il n'y a en vérité aucun mal à faire cela, la compréhension pouvant se faire à-partir de la réflexion d'autrui... surtout en ce qui concerne les démonstrations).
Mais passons !
christophe c écrivait : http://www.les-mathematiques.net/phorum/read.php?34,1007303,1007423#msg-1007423
Utiliser une propriété pour faire une démonstration, n'est-ce pas un petit peu trop facile ? :-/ Je ne pense pas que ça correspondra à la correction du prof.
Pour la 4, je peux raisonner par récursivité tu penses ? Genre on considère le sommet 0, 1, 2... n-1 et pour chacun d'eux, comme tu l'as dit, on regarde ses voisins. La récursivité me semble toute indiquée.
[Inutile de recopier des messages précédents. Le lien suffit. AD] -
3 mais c'est pour tinviter à la prouver justement cette propre
Tu peux aussi enlever des arêtes jusqu'à plus possible sans déconnecter le graphe. Puis tu en enlèves une de plus deconnectante.. -
Pour la 4, je peux raisonner par récursivité tu penses ? Genre on considère le sommet 0, 1, 2... n-1 et pour chacun d'eux, comme tu l'as dit, on regarde ses voisins. La récursivité me semble toute indiquée.
La mot récursivité est utilisé dans d'autres sens généralement, pour programmer ou comme propriété de certaines fonctions. Là, tu souhaites prouver quelque chose, donc c'est plutôt le mot récurrence.
Dans 3 comme dans 4, je te conseille de prendre le plus petit graphe éventuel à être contre-exemple à ton affirmation et à montrer qu'il ... n'existe pas.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Bonjour,
Pour la 4, je te conseille d'utiliser le principe du Pigeonhole (si on doit répartir n+1 pigeons parmi n cages, alors au moins 1 cage contient au moins 2 pigeons). -
@BenStanou: dit comme ça, faut prendre quelques précautions et utiliser les composantes connexes. Dans un graphe à n sommets, non orienté, le nombre de voisins d'un sommet est dans $\{0;\dots ; n-1\}$ qui comporte $n$ éléments et non pas $n-1$ éléments. Par ailleurs, pour les graphes orientés, le résultat est faux, même en évitant les boucles. Donc tu as peut-être raison dans ton conseil, mais il y a un moment où il faudra probablement utiliser la non-orientation, et les composantes connexes. Ca sent de suite moins bon. Cela dit ça marche quand-même, t'inquiète, puisque ça oblige les composantes connexes à n'avoir qu'un seul élément donc à n'être "qu'une"
PardonAide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Je donne des indications de démonstrations. Ces quatre faits sont à la base de n'importe quel cours élémentaire de théorie des graphes.
1. Montrez qu'un graphe simple a un nombre pair de sommets de degré impair. J'ai ma petite idée : je pense utiliser la formule "la somme des degrés d'un graphe = 2*card(ensemble des arêtes)" en séparant la somme des degrés de sommets à degrés impairs de la somme des degrés de sommets à degrés pairs… mais je ne vois pas trop comment.
C'est en effet l'idée qu'il faut utiliser. Séparer dans la somme les degrés pairs des degrés impairs. Et utiliser "pair + impair = impair", "impair + impair = pair".
2. Démontrez le Lemme de Koenig. Pour rappel, il dit qu'il existe nécessairement une chaîne élémentaire entre deux sommets s1 et s2 reliés par une chaîne quelconque. C'est tellement intuitif que c'en devient impossible à démontrer…
Si une chaîne qui relie les sommets existe, il suffit d'en prendre une de longueur minimale : elle conviendra. Si cette chaîne n'était pas élémentaire un même sommet apparaîtrait deux fois, d'où la présence d'une cycle que l'on pourrait enlever en faisant décroître la longeur de la chaîne.
3. Démontrez que G connexe comporte au moins card(ensemble des sommets) - 1 arêtes.
On pourrait faire une démonstration par récurrence utilisant le fait qu'un graphe connexe possède un sommet tel que si on l'enlève ainsi que les arêtes adjacentes, le graphe obtenu reste connexe. Mais ce resultat est plus compliqué à démontrer.
Il faut s'inspirer de ça pour faire une démo plus élémentaire, toujours par récurrence. Pour passer du cas de n sommets à n+1 sommets, on raisonne comme suit. Si le graphe possède un sommet de degré 1, alors on peut l'enlever ainsi que l'arête adjacente et ce qui reste est connexe. On applique l'hypothèse de récurrence. Sinon tous les sommets sont de degrés >=2 et on écrit l'équation "(somme des degrés)/2 = nbre d'arêtes" et on s'en sort sans utiliser l'hypothèse de récurrence.
Si on connait bien les arbres on a une autre démo comme suit :
-- un arbre sur n sommets possède n-1 arêtes
- - tout graphe connexe possède un arbre couvrant.
Le résultat en découle trivialement.
4. Démontrez qu'il n'existe pas de graphe non-orienté ayant au moins deux sommets et tel que tous les sommets aient des degrés distincts.
Noter que les degrés possibles varient de 0 à n-1, où n est le nombre de sommets. S'ils était tous distincts chaque valeur possible serait prise une et une seule fois. Chercher alors une contradiction. Variante : utiliser le principe des tiroirs (Pingeonhole) en séparant les cas où il existe un sommet de degré n-1 ou pas. -
Tant qu'on y est, je détaille un peu plus mes suggestions puisqu'effectivement des preuves doivent figurer partout, et je crois que celles que j'ai suggérées sont moins "usuelles" disons, puisque proposées à l'arrache. Dans chaque cas, on suppose le graphe plus petit contre-exemple possible.
3) On peut supposer le graphe tel que la moindre arête enlevée le déconnecte. En levons-la. Il est à justifier qu'il n'y a ensuite que DEUX composantes connexes. La suite découle du fait que $((a-1)+(b-1))+1\geq (a+b)-1$.
4) On peut supposer qu'il y a un sommet s du graphe G qui a au moins 2 non voisins (à justifier). Le sous-graphe induit par les non voisins de s dans G vérifie la propriété donc G aussi. (L'inconvénient du pigeonhole est qu'il renvoie vers les composantes connexes)Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Ah pardon d'ailleurs mon argument pour (4) est non probant, il ne marche pas!!!
Bon bin je reprends la suggestion des autres: il n'y a qu'un seul sommet isolé éventuel et les n-1 autres sommets ont un degré qui appartient à $\{1;...;n-2\}$. Et si y en a pas, même genre d'argument de 3 mots.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Svp est-ce que vous avez une idée comment on montre qu'un graphe est connexe par l'absurde... c'est-à-dire on prend un sommet isolé et on continue la démonstration...
Je vous en remercie d'avance !! -
Bonjour, pour la partie 1.
a)Travailler sur chaque composante connexe.
b) Un arc est relié à deux sommets.
c) Tous les hommes devraient ranger eux-même leurs chaussettes.
Voici une démarche pour la partie 2 :
a) Prouver qu'une chaîne non élémentaire contient un ou des cycles.
b) Déconnecter les arcs des cycles qui "conviennent" jusqu'à obtenir une chaîne élémentaire.
A propos de "l'évidence" ; cette discipline n'est toujours pas enseignée au collège ou au lycée en France bien qu'importante!.
Partie 3 : Un graphe connexe contient une chaîne maximale dont il faut compter les sommets et les arcs et puis ajouter les arcs et sommets manquants (faire une récurrence en remarquant qu'on peut toujours ajouter un arc connecté à la chaîne )
Partie 4 : Prendre une chaîne élémentaire.maximale (elle a au moins deux sommets donc...). Faire une récurrence en ajoutant les arcs qui manquent . Que se passe-t-il pour les extrémités de cette chaîne?
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.1K Toutes les catégories
- 59 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres