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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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
pardon
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]
Tu peux aussi enlever des arêtes jusqu'à plus possible sans déconnecter le graphe. Puis tu en enlèves une de plus deconnectante..
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.
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).
Pardon
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.
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)
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.
Je vous en remercie d'avance !!
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?