Voilà une question qui peut paraitre gentille mais elle ne me parait pas évidente pour autant:
Je me donne un graphe - parfaitement quelconque , il peut être infini par exemple - et des résistances sur ses arrêtes. Comment calculer la résistance effective entre deux sommets de ce graphe? Si possible avec une méthode générale et surtout programmable.
Bon on peut quand même faire quelques hypothèse de type nombre de voisins bornés ou que-sais-je...
Merci à ceux qui y penseront.
bonjour il manque des précisions sur le graphe ? abscisses, ordonnées? f(x)=?
La logique est une méthode systématique d’arriver en confiance à la mauvaise conclusion.
Non j'entends un graphe G=(V,E) où V est un ensemble de sommet et E un ensemble d'arêtes , je veux dire de paires d'éléments de V. Électriquement ce sont des noeuds et des fils.
La question est donc le calcul d'un nombre quelqconque de resistances quelconques connectées de manière quelconques (ça fait beaucoup de quelconque) ou au moins d'une bonne approximation.
je comprends encore moins, un petit schéma vaut mieux qu'un long discours !
La logique est une méthode systématique d’arriver en confiance à la mauvaise conclusion.
Admettons que je te donne ce dessin: chaque trait est une résistance ayant la valeur écrite à coté (disons en ohms) . Ca te fait un joli circuit électrique et je te demande la resistance effective entre A et B. (Formellement le rapport tension / intensité si je branche un générateur sur AB)On l'a tous fait des dizaine de fois sur un exo d'electricité, mais peut-on trouver un algorithme de calcul général? Sachant qu'il peut y avoir une infinité de sommets...(c'est là que ça devient utile en fait).Voilà.
PS: Le graphe lui-même , sur mon dessin ce serait une numérotation des sommets et une liste qui contient les couple de sommets que j'ai reliés.
ah ! la je vois de quoi on parle
oui il y a des algorithmes, il sont utilisé dans les logiciel de simulation électronique.
je ne suis pas spécialiste, c'est un calcul matriciel qui résout tout les courants est toutes les tentions du circuit, mais je ne connais pas l'algorithme qui remplie les matrices (c'est la résolution de N équation a N inconnue, N étant le nombre de mailles du circuit);
La logique est une méthode systématique d’arriver en confiance à la mauvaise conclusion.
Merci beaucoup je vais chercher tous ça..Mais euh...et s'il y a un nombre infini de sommets? c'est faisable? en ayant une certaine régularité du graphe?parce que la resolution matricielle en taille infini j'ai un peu de mal^^"
Bonsoir,
je pense que cela doit etre proche des problemes de réseau de transport
http://www.enseignement.polytechniqu.../beal/opt.html
j'envisagerai cela en commencant par chercher le chemin le plus économique (la resistance la plus faible), cela donne déja un maximum à la resistance du reseau (ce n'est pas le résultat, mais cela te donne déja une borne)
Aprés, je crois que j'essairais en partant d'un coté ou de l'autre du réseau d'appliquer des successions de transformations etoile/triangle afin de pouvoir progresser dans le réseau.
fred
mmmm...sauf que la resistance minimale, c'est le problème du voyageur de commerce qui est typiquement impraticable informatiquement...
Bonjour,
je ne pense pas que les problemes soient semblables, dans le cas du probleme du voyageur de commerce, tu cherches à faire un reseau qui à un seul cycle, dans le cas qui nous interesse, a chaque fois que tu trouves un sous reseau connecté au reste par 2 ou trois points tu peux simplifier définitivement cette partie pour ne pas revenir dessus.
Dans le cas du calcul de cette resistance, il peut eventuellement être realisé par une succession de simplifications locales.
tu peux dans le cas present creer de proche en proche des reseaux equivalents de moins en moins complexes.
donc il ne s'agit vraisemblablement pas d'un probleme NP complet.
fred
Re Bonjour,
il faudrait éventuellement voir si le theoreme de Kennely n'est pas généralisable à d'autres polygones que le triangle. cela te donnes alors directement une solution possible du probleme en un temps polynomial
fred
bonjour,
un petit exemple des differentes phases pour reduire de proche en proche le nombre de noeuds.
ce sont des methodes locales qui remplacent une partie du réseau par une partie equivalente et donc qui ne prennent pas à chaque étape en compte la totalité du reseau.
cela garanti à ton probleme un temps de resolution polynomial
fred
merci beaucoup pour ces réponses, je vais essayer de partir sur cette piste. L'idée de restreindre une partie du réseau me parait pas mal. Avec le principe de Thompson cela donne une borne supérieure(on déconnecte du reste du réseau donc on augmente la résistance entre les deux points) et de plus on se ramènerai à un graphe fini qui après quelques essais se resouds effectivement par inversion matricielle soit O(n²). Je vais regarder si on ne peut pas faire mieux avec Kennely...
Euh...ta pièce jointe ne passe pas...tu pourrait essayer avec un schéma par imageshack ou quelque chose du genre?
bonjour,
il faut attendre qu'un moderateur la valide, mais si tu es pressé, passes moi ton mail en MP et je te l'envoie
fred
