En mathématiques, la théorie topologique des graphes est une branche de la théorie des graphes . Elle étudie entre autres les plongements de graphes dans des surfaces, les graphiques en tant qu'espaces topologiques ainsi que les immersions de graphes.
Un plongement d'un graphe dans une surface donnée, une sphère par exemple, est une façon de dessiner ce graphe sur cette surface sans que deux arêtes se croisent. Un problème fondamental de la théorie topologique des graphes, souvent présenté comme un casse - tête mathématique, est le problème des trois chalets. D'autres applications existent comme dans l'impression de circuits électroniques où le but est d'imprimer (trouver un plongement) un circuit (le graphe) sur une carte de circuit imprimé (la surface) sans que deux connexions se croisent et provoquent un court-circuit .
À un graphe non orienté donné, on peut associer un espace topologique ainsi : chaque sommet est représenté par un point, et chaque arête est un arc homéomorphe à qui relie ses deux extrémités. Avec ce point de vue, on peut définir la notion d'homéomorphisme de graphe découlant directement de celle d'homéomorphisme topologique. De plus la notion de graphe connexe coïncide avec la connexité topologique et un graphe connexe est un arbre si et seulement si son groupe fondamental est trivial.
John Hopcroft et Robert Tarjan ont inventé un algorithme pour tester la planarité d'un graphe en temps linéaire en le nombre d'arêtes. Un test de planarité efficace est un outil fondamental pour le tracé des graphes.
Fan Chung et al. ont étudié le problème du plongement d'un graphe dans un livre, en tant qu'espace topologique constitué de feuilles ayant un bord commun, de sorte que les sommets du graphe soient dans ce bord commun. Ses arêtes sont dessinées sur des pages séparées de telle sorte que les arêtes plongées sur une même page ne se croisent pas. Ce problème apparait notamment en pratique lors du routage de cartes de circuits imprimés multicouches.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Dans le domaine mathématique de la théorie des graphes, un arbre couvrant d'un graphe non orienté et connexe est un arbre inclus dans ce graphe et qui connecte tous les sommets du graphe. De façon équivalente, c'est un sous-graphe acyclique maximal, ou encore, un sous-graphe couvrant connexe minimal. Dans certains cas, le nombre d'arbres couvrants d'un graphe connexe est facilement calculable. Par exemple, si lui-même est un arbre, alors , tandis que si est un n-cycle, alors .
En théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal.
Lattice models consist of (typically random) objects living on a periodic graph. We will study some models that are mathematically interesting and representative of physical phenomena seen in the real
Explore les algorithmes de consensus qui varient dans le temps dans les systèmes de contrôle en réseau et le rôle de la matrice laplacienne dans l'obtention d'un consensus moyen.
Explore l'inférence des connaissances pour les graphiques, en discutant de la propagation des étiquettes, des objectifs d'optimisation et du comportement probabiliste.
Explore les algorithmes de consensus dans les systèmes de contrôle en réseau, couvrant des sujets tels que les modèles Metropolis-Hasting et le calcul distribué de régression des moins-quaires.
This paper investigates causal influences between agents linked by a social graph and interacting over time. In particular, the work examines the dynamics of social learning models and distributed decision-making protocols, and derives expressions that rev ...
2023
, , ,
The adaptive social learning paradigm helps model how networked agents are able to form opinions on a state of nature and track its drifts in a changing environment. In this framework, the agents repeatedly update their beliefs based on private observation ...
In this paper, we propose a novel approach that employs kinetic equations to describe the collective dynamics emerging from graph-mediated pairwise interactions in multi-agent systems. We formally show that for large graphs and specific classes of interact ...