Arranger un graphe, de quelle manière?

[invite909be3f8]

Bonsoir!
Je suis en TS spé maths, je "m'amusais" à faire un arbre des notions en physique, c'est à dire de relier toutes les notions entre-elles et former une sorte d'encyclopédie des notions.
Ca ressemble à ça:



Je voudrais le réarranger de sorte à ce qu'il y aie le moins de croisements possible entre des connections. (Aïe)
Puisque certaines notions sont plus importantes que d'autres par leur poids (nombre de liaisons), je me suis dis qu'il y avait peut-être moyen d'organiser tout ça avec des maths?
J'avais étudié un cas similaire avec des matrices pour organiser un site internet en fonction du nombre de vues de chaque page...

Du coup j'en ai parlé à mon prof de spé, il m'a dit que ça touchait à la théorie des graphes, mais qu'il ne s'y connaissait pas assez pour me répondre quoique ce soit...
Déterminer le poids de chaque notion, ça va, je peux faire un tableau avec chaque notion et son nombre de connections... Mais du coup, est-ce que ça mène à quelque chose?
A votre avis, y aurait-il une méthode pour réarranger tout cela avec des maths, où bien je dois le faire manuellement en tâtonnant?
Parce que je vois pas trop comment une loi mathématique pourrait m'aider là-dedans

Merci!
-----

[invite9dc7b526]

Tu peux déjà chercher si ton graphe est planaire et pour cela utiliser la CNS du théorème de Kuratowski.

[invite909be3f8]

Ben il n'est pas planaire je crois, du coup il n'y a pas moyen de l'optimiser?

[invite9dc7b526]

Il existe des algorithmes permettant de dessiner sans intersections un graphe planaire. Il est possible qu'il en existe pour dessiner un graphe non planaire avec le moins d'intersections possible, mais je ne sais pas si ça a un intérêt suffisant pour que quelqu'un se soit attaché à le développer.

[A voir en vidéo sur Futura]

[pm42]

Il est possible qu'il en existe pour dessiner un graphe non planaire avec le moins d'intersections possible, mais je ne sais pas si ça a un intérêt suffisant pour que quelqu'un se soit attaché à le développer.

Il y a des trucs qu'on trouve en faisant une recherche en anglais. C'est quand même pointu pour un TS.
Le plus simple serait d'utiliser un outil comme Maple ou une librairie.

Mais effectivement, il y a une forte concentration des méthodes et infos sur les graphes planaires parce que sinon, la représentation peut vite devenir n'importe quoi.
D'ailleurs, la question se pose de l'intérêt d'un tel graphe de concepts s'il n'est pas planaire : est ce qu'un humain va s'y retrouver ? Je pense au contraire que cela va vite devenir confus.

Une solution serait de le rendre planaire en se concentrant sur les liens importants uniquement. Ensuite, si on veut en mettre d'autres, on les trace dans une couleurs très légère. Bref, on affiche une superposition de graphes planaires.

[gg0]

Il y a une autre possibilité, qui est d'éviter de mélanger des notions de niveaux très différents, comme principe de moindre action et constante de Boltzmann; ou mécanique des fluides et corps noir. Donc trier et hiérarchiser les notions. Ce qui demande de les comprendre vraiment ...

Cordialement.

[invite909be3f8]

En fait ce n’était qu’un brouillon que j’ai fait au fil des articles wikipedia, à chaque notion il renvoie vers d’autres, et c’est comme ça que j’ai construit ce graphe
L’histoire de superposition de graphes m’a l’air intéressante, je vais y aller pour ça!
Merci!

[invite51d17075]

Il y a une autre possibilité, qui est d'éviter de mélanger des notions de niveaux très différents, comme principe de moindre action et constante de Boltzmann; ou mécanique des fluides et corps noir. Donc trier et hiérarchiser les notions. Ce qui demande de les comprendre vraiment ...

Cordialement.

j'allais faire la même remarque, mais trop tard.... grillé.

[invite23cdddab]

Il y a des méthodes pour représenter des graphes complexes, qui sont basées sur la machine learning.

Par exemple, ici une représentation de 100.000 pages de wikipedia et leurs relations :

http://wiki.polyfra.me/#

[invite9dc7b526]

c'est joli! dans le même esprit (mais quand-même plus simple) les gens qui font de la génomique ont développé toutes sortes de représentations graphiques des relations entre gènes ou entre génomes.

[pm42]

Et tout ça est facilement accessible à un élève de Terminale S ?