Bonjour,

je voulais savoir quelle est l'utilité de la représentation des graphes dans la vie réel, svp on cherche de spécificité c-a-dire :

type de graphe ->  quelque utilité dans la vie.

merci

Par exemple tu as les grosses villes de France qui représentent des noeuxs, tu as des routes reliant des paires de villes représentants des arêtes, et tu cherches à relier toutes les villes entre elles en cherchant à réduire le coût de construction de routes. Ici tu veux donc un sous graphe convexe de poids minimal (le poids d'une arête étant le coût d'une arête, elle peut être proportionnelle à la longeur de la route par exemple). Cela s'appelle chercher un sous arbre couvrant minimal.

Tu peux regarder aussi tu côté des flots. Tu peux utiliser des graphes pour par d'un réseau informatique par exemple.

Pour la recherche du sous-arbre couvrant de poids minimal, je pense qu'il sied mieux à un problème de câble électrique : relier une centrale aux villes qu'elle dessert, relier un transformateur en ville aux maisons associées, etc.

Honnêtement, tchiko23, je trouve ta question assez intrigante, j'ai l'impression de chercher à quoi les fonctions peuvent servir dans la vie... Il y a tellement de choses...

Mais je peux essayer d'en trouver quelques unes qui me viennent en tête...

Par exemple, si tu considère la carte de France, tous les branchements sont les sommets d'un graphe dont les routes sont les arrêtes. Aller d'un point A à un point B, c'est trouver un chemin dans ton graphe. Un GPS qui te trouve le chemin le plus rapide pour rentrer chez toi résout donc un problème de plus court chemin dans un graphe (plan).

Si tu considère les graphes d'intervalles (qui est un type particulier de graphe), cette vidéo donne une application un peu sortie de nulle part, mais super intéressante à mon gout : https://www.youtube.com/watch?v=ZGhSyVvOelg
Si tu t'intéresse aux maths, je te conseille d'ailleurs toutes les vidéos de cette chaîne. D'ailleurs cette vidéo aussi parle de graphes (bipartis et planaires, ici) : https://www.youtube.com/watch?v=zxJzHzt9z3o

Mais sinon, une puce électronique (ou un circuit électrique), c'est un graphe. Un personnage dans un jeu vidéo, c'est un graphe (pour traiter son image). Internet, c'est un graphe. etc.

J'ai donné beaucoup d'exemples avec des graphes non orientés. On parle pas mal de graphes orientés en grande partie parce que c'est un cas plus général : un graphe non orienté n'est qu'un graphe orienté vérifiant "(a,b) est une arrête si et seulement si (b,a) en est une". Généralement, d'ailleurs, on utilise un graphe orienté pour représenter informatiquement un graphe non orienté.

Mais il existe bien sûr des exemples faisant intervenir des graphes orientés : par exemple, un programme informatique se modélise en un graphe orienté donc chacune des lignes est un noeud, et une arrête représente le fait de "pouvoir passer d'une action à l'autre". On peut utiliser cette représentation quand on cherche à compiler le graphe.
En 5e, en techno, je me souviens avoir fait des schémas (je me souviens plus le nom) avec des rectangles et des losanges pour représenter un fonctionnement automatisé... Mais ce truc était totalement un graphe (même si ça a l'air peu utile de faire de la théorie des graphes dessus...)
Sinon, pour revenir à nos cartes, pour avoir des sens uniques, faut de la non-orientation...

...Et il y a plein de types "plus spécifiques", mais si je prend un type de graphe quelconque j'aurais encore des exemples parfaitement différents à présenter, et on a pas "un type pour un problème" comme ta demande le fait penser...

-
Edité par Grob' 26 juillet 2016 à 21:02:01

Merci a vous pour vos réponses,cependant en ceux qui concerne 'plus spécifiques' je voulais savoir l'utilité du graphe bipartie par exemple car je récolte quelque information afin de choisir un graphe et discuter son nombre chromatique et faire un calcule probabilisée .

pour vos exemple je vous dit merci ,mais ce son les exemples les plus populaires au monde de la théorie des graphes (flux de transport,réseaux informatique,représentation des maps ,...), je cherche quelque cas extrême la ou on montre l'utilité de la théorie des graphes (exemple : on modélise un texte sous forme d'un programme linéaire (recherche opérationnelle ) y a quelque cas qu'il faut absolument utiliser la théorie des graphes pour extraire la solution ).

 @Grob' je suis intéresser par les maths ouii

Les maths, c'est un outil. Si tu veux enfoncer un clou, il y a l'outil adapté (la marteau), mais tu peux aussi planter un clou avec ta chaussure... Donc chercher des cas où il faut absolument utiliser la théorie des graphes, c'est un peu vain...

Oui, on t'a donné des exemples populaires, mais tu n'as pas été très très explicite dans ta demande...

Mais ta demande est assez dure à donner. Si tu me demande quelles sont toutes les utilités d'un marteau, je te donnerais sûrement "planter un clou", "enfoncer un truc" (j'ai pas le mot précis en tête ><'), mais quelqu'un a sûrement déjà du tenter d'ouvrir une boite de conserve à l'aide d'un marteau et réussi...
...Pourtant, si tu me donne une boîte de conserve, un truc pointu et un marteau, je serais sûrement capable d'ouvrir cette boite...

De la même manière, si tu me donne un problème à résoudre, je pourrais chercher un graphe précis pour trouver la solution, mais demander tous les problèmes qu'on peut résoudre à l'aide de graphes, c'est vraiment pas évident...
...Et en plus je vois mal en quoi ça peut t'aider...

Bref, là, comme ça, je vois pas, si j'ai une idée qui me vient prochainement je penserais à toi

tchiko23 a écrit:

Merci a vous pour vos réponses,cependant en ceux qui concerne 'plus spécifiques' je voulais savoir l'utilité du graphe bipartie par exemple car je récolte quelque information afin de choisir un graphe et discuter son nombre chromatique et faire un calcule probabilisée .

pour vos exemple je vous dit merci ,mais ce son les exemples les plus populaires au monde de la théorie des graphes (flux de transport,réseaux informatique,représentation des maps ,...), je cherche quelque cas extrême la ou on montre l'utilité de la théorie des graphes (exemple : on modélise un texte sous forme d'un programme linéaire (recherche opérationnelle ) y a quelque cas qu'il faut absolument utiliser la théorie des graphes pour extraire la solution ).

 @Grob' je suis intéresser par les maths ouii

Bonjour,

Alors dans la vie réelle de tous les jours →

• plan de table pour couples avec certaines contraintes, par exemple un époux ne doit pas être assis à côté de sa femme mais pas trop loin non plus (à 4 place maximum). Il y les cas table rectangulaire, circulaire, etc …
• résolution d'énigmes policières
  «Il y a quelques années, le Duc de Densmore périt dans l'explosion qui détruisit son château. Son testament fut détruit ; or celui-ci avait tout pour déplaire à l'une de ses sept ex-femmes.
  Peu avant le crime, elles étaient toutes venues au château et elles jurèrent que ce fut la seule fois où elles s'y étaient rendues. Elles peuvent donc toutes être coupables, mais le dispositif ayant provoqué l'explosion avait été dissimulé dans une armure dans la chambre du Duc, et sa pose avait nécessité plus d'une visite. Donc la coupable a menti : elle est venue plusieurs fois.
  Ann dit avoir rencontré Betty, Charlotte, Félicia et Georgia ; Betty dit avoir rencontré Ann, Charlotte, Edith, Félicia, et Helen ; Charlotte dit avoir rencontré Ann, Betty et Edith ; Edith dit avoir rencontré Betty, Charlotte et Félicia ; Félicia dit avoir rencontré Ann, B e t t y, Edith et Helen ; Georgia dit avoir rencontré Ann et Helen ; Helen dit avoir rencontré Betty, Félicia et Georgia.»
• ...

Je ne sais pas ce que tu entends par "dans la vie réelle" mais il s'agit avant tout d'une modélisation, bien que par exemple les aéroports et les voies aériennes les reliant constituent un excellent exemple concret de ce qu'est un graphe.

Si ça t'intéresse j'ai eu à mes concours de CPGE un sujet montrant comment répondre à certaines problématiques (utiles dans les moteurs de recherche par exemple) en modélisant internet par un graphe dont les sommets sont les sites et les arcs les liens d'un site à un autre (j'ignore ton niveau d'étude mais au moins lire le sujet est intéressant) : https://al9ahira.files.wordpress.com/2016/04/mines-option-info-2016e.pdf

@PicoDev merci beaucoup.

@Shinra_Fr je suis en 4éme année info, merci pour la documentation