Séance de cours

Graphiques et matrices

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre l'étude des graphiques et des matrices, en mettant l'accent sur des concepts importants tels que la matrice d'adjacence, la matrice de degré et la matrice de Laplace d'un graphique. Il s'enfonce également dans le théorème des arbres matriciaux et le nombre d'arbres qui s'étendent. L'instructeur explique l'interprétation des entrées dans les matrices, les matrices d'incidence, et les marches dans les graphiques, fournissant des exemples et des preuves pour améliorer la compréhension.

Source officielle

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Algèbre: Algèbre linéaire

Concepts associés (32)

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.

Matrice d'adjacence

En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à n sommets est une matrice de dimension n × n dont l'élément non diagonal a est le nombre d'arêtes liant le sommet i au sommet j. L'élément diagonal a est le nombre de boucles au sommet i (pour des graphes simples, ce nombre est donc toujours égal à 0 ou 1). Cet outil mathématique est très utilisé comme structure de données en informatique (tout comme la représentation par liste d'adjacence), mais intervient aussi naturellement dans les chaînes de Markov.

Matrice binaire

Une matrice binaire est une matrice dont les coefficients sont soit 0, soit 1. En général ces coefficients sont les nombres de l'algèbre de Boole dans laquelle on appelle B l'ensemble constitué de deux éléments appelés valeurs de vérité {VRAI, FAUX}. Cet ensemble est aussi noté B = {1, 0} ou B = {⊤, ⊥}. On privilégie souvent la notation B = {1, 0}. Quand on programme des algorithmes utilisant ces matrices, la notation {VRAI, FAUX} peut coexister avec la notation {1, 0} car de nombreux langages acceptent ce polymorphisme.

Matrice d'incidence

En mathématiques, et plus particulièrement en théorie des graphes, la matrice d'incidence d'un graphe est une matrice qui décrit le graphe en indiquant quels liens arrivent sur quels sommets. La matrice d'incidence est une matrice n x p, où n est le nombre de sommets du graphe et p est le nombre de liens (arêtes ou arcs). Cette matrice est définie de deux façons différentes selon que le graphe est orienté ou non orienté.

Arbre couvrant

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 .

Afficher plus

Séances de cours associées (64)

Pseudorandomité : théorie et applications

Explore la théorie pseudo-aléatoire, les défis de l'IA, les graphiques pseudo-aléatoires, les marches aléatoires et les propriétés de la matrice.

Modèles graphiques : Représentation des distributions probabilistes

Couvre les modèles graphiques pour les distributions probabilistes à l'aide de graphiques, de nœuds et de bords.

Pseudo Randomness dans les graphiques

Explore le pseudo-aléatoire dans les graphes en utilisant des valeurs propres et des polynômes, en soulignant l'importance des racines groupées et des entrelaceurs communs.

Graphes et réseaux : bases et applications

Présente les bases des graphiques et des réseaux, couvrant les définitions, les chemins, les arbres, les flux, la circulation et les arbres couvrants.

Graphiques et probabilités

Explore le lien entre les graphiques et les probabilités, en mettant l'accent sur les probabilités modulaires et super modulaires et les propriétés de corrélation.

Afficher plus

Concepts associés (32)