Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
170 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Théorie des graphes : 4 démonstrations ?

Envoyé par Odysay 
Théorie des graphes : 4 démonstrations ?
il y a six années
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.
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
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?
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
Citation

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

pardon

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 2 fois. La dernière correction date de il y a six années et a été effectuée par christophe c.
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
Bonjour tout le monde,

Tout d'abord, merci d'avoir pris le temps de m'aider. :)

Je souhaite notamment répondre à depasse :
depasse écrivait : [www.les-mathematiques.net]
-------------------------------------------------------
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 : [www.les-mathematiques.net]
-------------------------------------------------------
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]



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par 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..
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
Citation

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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
BenStanou
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
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).
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
@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"

Pardon

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par christophe c.
Paul Broussous
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
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.
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
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)

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par christophe c.
Re: Théorie des graphes : 4 démonstrations ?
il y a six années
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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par christophe c.
Re: Théorie des graphes : 4 démonstrations ?
il y a trois mois
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 !!



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 744, Messages: 1 499 661, Utilisateurs: 28 309.
Notre dernier utilisateur inscrit erkl.


Ce forum
Discussions: 886, Messages: 7 507.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page