Théorie des graphes

[Pseuda]

Bonjour,

J'étudie (ou plutôt j'approfondis) actuellement la théorie des graphes pour mes élèves de TeES spé maths (théorie qui n'était pas au concours du capes externe que j'ai passé il y a 15 ans).

Question : est-ce que cette théorie est au programme du capes aujourd'hui ?

J'avoue que je suis un peu déçue par cette théorie, qui ne donne pas beaucoup de "beaux" résultats mathématiques ; exemples :
- elle ne rend pas compte de toutes les situations, notamment celles multi-partites (arêtes reliant 3 ou plusieurs sommets, jeu ou tournoi faisant intervenir plus de 3 participants, incompatibilité de 3 ou plusieurs produits chimiques...)
- elle ne donne pas de solutions mathématiques à bien des problèmes utiles : reconnaissance de graphes hamiltoniens, et en donne à des problèmes moins prégnants (graphes eulériens),
- les définitions sont souvent floues (combien d'arêtes possibles dans un graphe orienté...)
- des notions n'apparaissent pas d'une grande utilité : matrice d'adjacence (qui permet de déterminer en l'élevant à une puissance le nombre de chemins d'une certaine longueur), graphe eulérien, ... , à part de faire réfléchir les élèves.

Au final, cette théorie paraît incomplète et somme toute empirique (fonctionne beaucoup par algorithmes), et donne des résultats dont on n'a pas besoin, et n'en donne pas pour des situations plus intéressantes.

Est-ce que quelqu'un aurait un retour d'expérience sur cette théorie, pour infirmer ou confirmer cette impression ?

[Rockleader]

Salutation,

alors pour ma part, j'en ai fais l'an dernier en Licence 3 informatique, et on va pas se mentir, on ne trouve pas des résultats mathématiques révolutionnaire...

Malgré tout, moi j'ai trouvé ça plutôt intéressant, de voir des algo comme celui de Bellman Ford, mais c'est peut être uniquement parce qu'ils sont repris dans d'autres domaines de l'informatique comme les réseaux, donc mon point de vue est un peu biaisé sur la question.

je vais reprendre mon exemple de réseau sur ce point là:

- des notions n'apparaissent pas d'une grande utilité : matrice d'adjacence (qui permet de déterminer en l'élevant à une puissance le nombre de chemins d'une certaine longueur), graphe eulérien, ... , à part de faire réfléchir les élèves.

Pouvoir déterminer le chemin à prendre pour une connexion, chemin qui sera le moins coûteux possible, cela me semble tout sauf inutile et c'est même primordial dans les algo de routage dynamique.
D'un point de vue purement math, peut être que ça ne sert à rien, mais si on va dans ce sens, les math ne servent à rien du tout, on fais pas des math pour faire des math, on fait des math pour les appliquer dans un domaine auquel ils seront utile.

- les définitions sont souvent floues (combien d'arêtes possibles dans un graphe orienté...)

Les définitions ne me semblent pas floues du tout, je ne me rappelle plus de tout ce que j'ai fais là dessus, mais on pouvait parfaitement estimer ce nombre là, et heureusement d'ailleurs.

Au passage, attention sur tes définitions, une arrête c'est pour un graphe non orienté, si tu parles de graphe orienté, alors tu as des arcs et non des arrêtes.

- elle ne rend pas compte de toutes les situations, notamment celles multi-partites (arêtes reliant 3 ou plusieurs sommets, jeu ou tournoi faisant intervenir plus de 3 participants, incompatibilité de 3 ou plusieurs produits chimiques...)

Plus trop sûr de comment on appelle ça, mais il me semble qu'il s'agit de la méthode dite de coloration. Tu peux parfaitement traiter ce genre de problème ainsi.

[Pseuda]

Salutation,

alors pour ma part, j'en ai fais l'an dernier en Licence 3 informatique, et on va pas se mentir, on ne trouve pas des résultats mathématiques révolutionnaire...

On est bien d'accord, cela me rassure que tu penses comme moi.

Malgré tout, moi j'ai trouvé ça plutôt intéressant, de voir des algo comme celui de Bellman Ford, mais c'est peut être uniquement parce qu'ils sont repris dans d'autres domaines de l'informatique comme les réseaux, donc mon point de vue est un peu biaisé sur la question.

Je la trouve aussi très intéressante, et nécessaire comme faisant partie du champ des mathématiques / informatique / algorithmique, mais je suis surprise de voir que les résultats mathématiques sont faibles.

Pouvoir déterminer le chemin à prendre pour une connexion, chemin qui sera le moins coûteux possible, cela me semble tout sauf inutile et c'est même primordial dans les algo de routage dynamique.
D'un point de vue purement math, peut être que ça ne sert à rien, mais si on va dans ce sens, les math ne servent à rien du tout, on fais pas des math pour faire des math, on fait des math pour les appliquer dans un domaine auquel ils seront utile.

Pour ce genre de problème oui c'est bien utile, mais pour les problèmes vus en Te ES, il est quand même plus naturel par exemple, de chercher à passer par chacune des salles d'un musée une fois et une seule, que de chercher à passer par toutes les portes une fois et une seule. Dans un circuit touristique, il est plus naturel de vouloir faire toutes les villes en s'économisant les doublons que toutes les routes...

Les définitions ne me semblent pas floues du tout, je ne me rappelle plus de tout ce que j'ai fais là dessus, mais on pouvait parfaitement estimer ce nombre là, et heureusement d'ailleurs.

Pas d'accord. Toujours par rapport au programme de Te ES, il faut s'y reprendre à plusieurs fois pour comprendre ce qui rentre dans le champ d'une définition, et ce qui n'y rentre pas, surtout que le vocabulaire est très étendu.

Au passage, attention sur tes définitions, une arrête c'est pour un graphe non orienté, si tu parles de graphe orienté, alors tu as des arcs et non des arrêtes.

Au lycée, le vocabulaire est le même pour les graphes orientés ou non (on parle d'arêtes et non d'arcs pour des graphes orientés)

Plus trop sûr de comment on appelle ça, mais il me semble qu'il s'agit de la méthode dite de coloration. Tu peux parfaitement traiter ce genre de problème ainsi.

Toujours avec un algorithme. De mémoire, les mathématiques ne servent pas pour résoudre ce problème.

[Rockleader]

A l'époque où j'ai passé mon bac il y a 4 ans en Ts, l’algorithmique avait été inclus au programme en math, donc je ne pense pas que l'on puisse les dissocier l'un de l'autre à présent.

Pour ce qui est des définition, j'ai jamais trop aimé ce genre de principe ou on donne des définitions fausses.

Je peux comprendre l'idée d'avoir des définition incomplète, par exemple, dire qu'il n'y a aucune solution à une équation lorsque le discriminant est négatif, tant que les élèves ont pas vu les complexes, c'est tout à fait légitime. Mais, pas de définition comme celle là, arc, arrête, et bien disons que je vois pas ce que ça apporte de ne pas donner une définition complète.

Sa me rappelle le jour où quelqun m'a dit que la racine carré c'était la puisse 1/2. A partir de ce moment là j'ai fais mes calculs de racine avec des puissances, et le prof est venu me dire que c'était faux, parce qu'on avait pas vu ça en cours et que j'avais pas le droit de le faire...non, à la place il fallait perdre du temps à donner des résultat approché à la calculatrice x)

Enfin bref, je fais pas les programmes, et je peux comprendre, que vous prof, soyez obligé de suivre un programme, mais il faut parfois savoir prendre des libertés pour donner l'envie aux élèves. M'enfin, ça c'est que mon avis d'élève...

il est quand même plus naturel par exemple, de chercher à passer par chacune des salles d'un musée une fois et une seule, que de chercher à passer par toutes les portes une fois et une seule.

Je vois pas vraiment la différence en fait, je n'ai peut être pas compris l'analogie des portes et des salles.

Disons que pour moi une arrête, ou un arc représentera un couloir. Un état du graphe représentera les salles.

Le genre de problème que je traitais l'an dernier nous faisait déterminer comment passer dans tous les états avec un coup minimal. Donc passer dans chaque salle en faisant le moins de pas possible ce qui est pour le coup je trouve plus logique.
Ici, on évite les cycles, donc on passe pas plus d'une fois par une salle.

Une autre vision du problème autoriserait les cycles à conditions qu'ils déterminent le plus court chemin. On a pas travaillé là dessus, mais je vois pas en quoi c'est pas possible, ce doit pas être bien sorcier de pondérer le coup d'un arc par deux pour prendre l'allez retour et d'estimer la moyenne de pas en fonction de chaque situation. Je veux dire par là, il n'y a pas de définition bien préscise là dessus c'est vrai, mais mathématiquement parlant c'est absolument pas un problème de trouver un résultat de ce genre, au final ce n'est ni plus ni moins que faire la moyenne des plus court chemins sans cycles, et de comparer cette moyenne avec les pires cas contenant des cycles, à ce moment là il faut simplement prendre l'hypothèse qu'une personne ne vas pas passer plusieurs fois dans un cycle si cela ne lui permet pas d'arriver dans une salle plus rapidement.

[Pseuda]

A l'époque où j'ai passé mon bac il y a 4 ans en Ts, l’algorithmique avait été inclus au programme en math, donc je ne pense pas que l'on puisse les dissocier l'un de l'autre à présent.

Je trouve que ce sont des démarches très différentes intellectuellement. L'algorithmique, on tâtonne, on réajuste, les mathématiques, on émet des conjectures et on démontre (mais je ne connais pas trop l'algorithmique qui n'était pas au programme il y a 15 ans).

Pour ce qui est des définition, j'ai jamais trop aimé ce genre de principe ou on donne des définitions fausses.

Je peux comprendre l'idée d'avoir des définition incomplète, par exemple, dire qu'il n'y a aucune solution à une équation lorsque le discriminant est négatif, tant que les élèves ont pas vu les complexes, c'est tout à fait légitime. Mais, pas de définition comme celle là, arc, arrête, et bien disons que je vois pas ce que ça apporte de ne pas donner une définition complète.

Pour prendre un exemple simple. Définition d'un graphe complet tiré d'un livre de TeES : "un graphe est dit complet si tous les sommets de ce graphe sont adjacents."
Mais alors : cette définition s'applique-t-elle aux graphes orientés, non orientés, les 2 ?, le graphe peut-il être multigraphe (plusieurs arêtes entre 2 sommets) ? un graphe avec un seul sommet est-il considéré complet ?... Il faut aller à la pêche aux exemples et exercices pour trancher.

L'enseignement en ES est plus intuitif qu'en S, mais quand même... ce n'est pas très satisfaisant.

Autre exemple : "une chaîne est une liste ordonnée de sommets telle que chaque sommet de la liste soit adjacent au suivant". Mais si le graphe est multigraphe, on peut emprunter plusieurs arêtes entre 2 sommets, ce n'est plus la même chaîne ou c'est la même ?

Un prof doit savoir répondre aux questions qu'il se pose lui-même.

Je vois pas vraiment la différence en fait, je n'ai peut être pas compris l'analogie des portes et des salles.

Disons que pour moi une arrête, ou un arc représentera un couloir. Un état du graphe représentera les salles.

Le genre de problème que je traitais l'an dernier nous faisait déterminer comment passer dans tous les états avec un coup minimal. Donc passer dans chaque salle en faisant le moins de pas possible ce qui est pour le coup je trouve plus logique.
Ici, on évite les cycles, donc on passe pas plus d'une fois par une salle.

Il me semble que dans un graphe tiré de la vie courante (le plus fréquent en ES), on est plus intéressé par les sommets que par les arêtes (qui ne sont que des moyens d'accéder aux sommets). Mais ce n'est peut-être effectivement pas le cas pour des problèmes d'optimisation.

Ici, on évite les cycles, donc on passe pas plus d'une fois par une salle.
Une autre vision du problème autoriserait les cycles à conditions qu'ils déterminent le plus court chemin. On a pas travaillé là dessus, mais je vois pas en quoi c'est pas possible, ce doit pas être bien sorcier de pondérer le coup d'un arc par deux pour prendre l'allez retour et d'estimer la moyenne de pas en fonction de chaque situation. Je veux dire par là, il n'y a pas de définition bien préscise là dessus c'est vrai, mais mathématiquement parlant c'est absolument pas un problème de trouver un résultat de ce genre, au final ce n'est ni plus ni moins que faire la moyenne des plus court chemins sans cycles, et de comparer cette moyenne avec les pires cas contenant des cycles, à ce moment là il faut simplement prendre l'hypothèse qu'une personne ne vas pas passer plusieurs fois dans un cycle si cela ne lui permet pas d'arriver dans une salle plus rapidement.

Mais les plus courts chemins sont déterminés par l'algorithmique, donc la moyenne des plus courts chemins aussi, tant qu'à faire ?

Enfin, il me semble que la théorie des graphes se coupe d'une grande partie des problèmes, en considérant qu'une arête ne peut avoir que 2 extrémités (et pas 3 ou plus). Dès lors, les arêtes et les sommets seraient interchangeables, et ne seraient que les 2 faces du même problème.

[Rockleader]

Enfin, il me semble que la théorie des graphes se coupe d'une grande partie des problèmes, en considérant qu'une arête ne peut avoir que 2 extrémités (et pas 3 ou plus). Dès lors, les arêtes et les sommets seraient interchangeables, et ne seraient que les 2 faces du même problème.

C'est vrai que là on se limite à ce niveau là.

Peut être y aurait il de la recherche à faire, voir si les propriétés restaient vrais avec des "noeuds" permettant d'aller dans plusieurs états. Honnêtement, je ne sais pas, peut être que ça a déjà été fait.

Pour les définitions, je ne sais plus, je ne m'en rappelle plus. Moi elle me paraissait claire, mais peut-être parce qu'on avait plus d'éléments.

Je trouve que ce sont des démarches très différentes intellectuellement. L'algorithmique, on tâtonne, on réajuste, les mathématiques, on émet des conjectures et on démontre (mais je ne connais pas trop l'algorithmique qui n'était pas au programme il y a 15 ans).

Tâtonner pour moi c'est comme conjecturer.

Après, démontrer un algorithme, ça se fait, il y a des méthodes (si mes souvenirs de L2 sont bons, c'est un truc que l'on appelle le PFC). D'ailleurs je crois me rappeler que c'est fait par un français.

[fatal_error]

L'algorithmique, on tâtonne, on réajuste, les mathématiques, on émet des conjectures et on démontre (mais je ne connais pas trop l'algorithmique qui n'était pas au programme il y a 15 ans).

Ben fatalement, un algorithme n'a pas pour but de démontrer quoique soit.
c'est juste une suite d'instructions pour décrire un processus avec une entrée E et une sortie S.
rien n'empêche de faire une conjecture sur la complexité de l'algo, la taille de la sortie S ou autre (et de la démontrer) mais en soit l'algorithme c'est juste une liste d'instructions.

Si tu nommes tatonnement le fait d'écrire des instructions au pif pour que d'une entrée E tu obtiennes une sortie S, oui et non.
Par exemple si j'ai un graphe planaire (embedded) avec des faces, et que je veux trouver pour un point donné à quelle face il appartient en max N instructions, je peux composer:
- je construis une triangulation hierarchie n(logn) (au pif)
- je fais une requete (logn)

C'est pas du tout au pif, j'enchaine des instructions (bien choisies parce que je connais leur complexité) pour arriver à mon but.

Concernant le manque de résultats sur les graphes je pense que le problème n'est pas qu'il n'y en a pas, mais plutot que ceux qui existent sont soient trop pointus, soient sur des graphes trop particuliers pour éveiller un quelconque intérêt (au moins) au lycée..

Ya quand même bcp de travail et résultats sur les complexités des algo liés aux graphes (cycles, faces, parcourt, modifications), mais c'est ptet plus "macro" que ce qu'on fait classiquement avec les théorêmes!

[Pseuda]

C'est vrai que là on se limite à ce niveau là.

Peut être y aurait il de la recherche à faire, voir si les propriétés restaient vrais avec des "noeuds" permettant d'aller dans plusieurs états. Honnêtement, je ne sais pas, peut être que ça a déjà été fait.

Pour les définitions, je ne sais plus, je ne m'en rappelle plus. Moi elle me paraissait claire, mais peut-être parce qu'on avait plus d'éléments.

Je me demande pourquoi ce n'est pas fait : aucun intérêt pratique ? aucun intérêt mathématique ou algorithmique ? problèmes trop difficiles ? aucun résultat ? Ou bien : avec des arêtes à 3 extrémités ou plus, on peut se ramener facilement à des arêtes à 2 extrémités (par un procédé qui m'échappe) ?

Tâtonner pour moi c'est comme conjecturer.

Après, démontrer un algorithme, ça se fait, il y a des méthodes (si mes souvenirs de L2 sont bons, c'est un truc que l'on appelle le PFC). D'ailleurs je crois me rappeler que c'est fait par un français.

Oui d'accord. Je trouve que la différence réside en fait plus dans le fait qu'en mathématiques on cherche à comprendre les raisons profondes, à se convaincre de la véracité des résultats (en les démontrant), à généraliser des résultats, etc... alors qu'en algorithmique on cherche à atteindre un résultat en l'optimisant (quelque soit la nature de l'optimisation), et que de ce fait, la nature de la réflexion n'est pas du tout la même, sans en mettre une au-dessus de l'autre.

[Pseuda]

Fatal Error, je croyais que certaines démonstrations mathématiques étaient obtenues par des procédés algorithmiques ?

Quand je dis par tâtonnements, je voulais parler de la mise au point finale de l'algorithme. Cela n'exclut pas bien sûr une phase de réflexion profonde et de recherche préalable pour étudier et déterminer un processus de développement (enfin de ce que je connais de l'algorithmique de mon expérience professionnelle).

Il est surprenant que la théorie des graphes n'obtienne pas des résultats pour des problèmes qui paraissent simples comme les graphes hamiltoniens, et que le théorème des 4 couleurs simple à énoncer soit si difficile à démontrer.

Pour répondre à Robot, j'ai étudié la théorie des graphes en général, puis comme elle est énoncée en ES. Il y a des divergences dans les définitions (par exemple, en ES le vocabulaire des graphes orientés est le même que celui des graphes non orientés), d'un auteur à l'autre, etc... . C'est pour cela que je dis que les définitions sont floues, pas rigoureuses, cela ne donne pas une impression globale de rigoureux.

En fait, ce qui m'étonne c'est que l'on n'arrive pas à "industrialiser" les graphes (par des matrices par exemple), comme on le fait dans l'algèbre linéaire par exemple, et qui donne des très beaux résultats.

Mais je suis d'accord qu'il y a des domaines, et c'est très surprenant, comme le Sudoku par exemple, où on n'arrive pas à échaffauder une théorie évidente et simple pour les résoudre.