Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Théorie spectrale des graphes
Résumé
En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée.
Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées . Chaque élément de la matrice d'adjacence du graphe est défini par :
La matrice des degrés est une matrice diagonale où les éléments correspondent au nombre de liens du sommet , c'est-à-dire à son degré. En utilisant cette matrice et la précédente, on peut également définir la matrice laplacienne non normalisée .
On obtient sa forme normalisée par , où est la matrice identité. On obtient aussi directement par chacun de ses éléments :
Enfin, la matrice d'incidence d'un graphe est la matrice de dimensions dans laquelle l'élément vaut 1 si le sommet est une extrémité de l'arête , et 0 sinon. On a l'ensemble de relations suivantes, où désigne la matrice identité :
Pour la matrice d'adjacence du line graph ,
Pour la matrice d'adjacence du graphe de subdivision ,
Le spectre d'une matrice est l'ensemble de ses valeurs propres ; si elles sont réelles, nous convenons de les classer : . Par extension, on parle du spectre du graphe. On rappelle que la multiplicité algébrique d'une valeur propre est la puissance du monôme dans le polynôme caractéristique (c'est-à-dire la multiplicité de la racine dans le polynôme caractéristique). Il est également possible de modifier le polynôme caractéristique pour prendre en compte d'autres propriétés du graphe : on considère par défaut le polynôme (appelé polynôme caractéristique du graphe), mais on peut aussi s'intéresser à des variantes telles que ou .
La matrice du graphe est définie positive, et elle ne peut être réduite si le graphe est connexe. Dans le cas d'un graphe non orienté, la matrice est symétrique et hermitienne, c'est-à-dire que où est la matrice adjointe de .
Source officielle
À propos de ce résultat
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.
Publications associées (1)
Space-Efficient Representations of Graphs
With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a sin
EPFL2022Concepts associés (20)
Graphe fortement régulier
En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier. Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que Toute paire de sommets adjacents a exactement λ voisins communs. Toute paire de sommets non-adjacents a exactement μ voisins communs. Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
Théorie spectrale des graphes
En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées .
Matrice laplacienne
En théorie des graphes, une matrice laplacienne, ou matrice de Laplace, est une matrice représentant un graphe. La matrice laplacienne d'un graphe G non orienté et non réflexif est définie par : où est la matrice des degrés de G et la matrice d'adjacence de G. Formellement : A la différence de la matrice d'adjacence d'un graphe, la matrice laplacienne a une interprétation algébrique ce qui rend son analyse spectrale fructueuse. Plus précisément la matrice correspond à l'opérateur de diffusion sur le graphe.
Cours associés (10)
MATH-602: Inference on graphs
The class covers topics related to statistical inference and algorithms on graphs: basic random graphs concepts, thresholds, subgraph containment (planted clique), connectivity, broadcasting on trees,
CS-455: Topics in theoretical computer science
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
ME-427: Networked control systems
This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun
Séances de cours associées (79)
Graphiques isogéniques: analyse spectrale et applications mathématiques
Explore les graphes isogéniques, les propriétés spectrales et les applications mathématiques sous des formes modulaires et cryptographiques.
Algorithmes de consensus: Assignation de poids et applications
Explore la conception de poids graphiques pour le consensus et les applications dans les réseaux de capteurs.
Calcul distribué : Algorithmes consensuels dans les systèmes de contrôle en réseau
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.