Mathématiques

Mathématiques

Matrices : graphes

Ta progression dans la leçon
 
 
0%

Résumé

Télécharger

Matrices : graphes

Graphes

Définition

Un graphe est un ensemble fini d’éléments (les points), appelé sommets, reliés entre eux par des arêtes (les segments).


Notions

ORDRE

L’ordre d’un graphe est son nombre de sommets.

DEGRÉ

Le degré d’un sommet est le nombre d’arrêtes qui le relient aux autres sommets.

ADJACENTS

Deux sommets sont adjacents s’ils sont reliés par une arête.

COMPLET

Un graphe est complet lorsque chacun de ses sommets est relié à tous les autres.  

ORIENTÉ

Dans un graphe orienté, les arêtes ont un sens. On représente généralement un tel graphe avec des flèches sur les arêtes.


Exemples
Mathématiques; Graphes; Tle générale; Matrices : graphes
Mathématiques; Graphes; Tle générale; Matrices : graphes

Graphe d’ordre 4. Le sommet A est de degré 2 et est adjacent aux sommets B et C.

Graphe complet d’ordre 5.
Mathématiques; Graphes; Tle générale; Matrices : graphes
Mathématiques; Graphes; Tle générale; Matrices : graphes

Graphe orienté

Graphe non orienté


Chaînes

Définition

Une suite d’arêtes consécutives forme une chaîne. Sa longueur est le nombre d’arêtes qui la composent. Si le sommet de départ est le même que celui d’arrivée, on dit que la chaîne est fermée.


S’il est possible de relier n’importe quelle paire de sommets du graphe par une chaîne, on dit que le graphe est connexe.


Exemples
Mathématiques; Graphes; Tle générale; Matrices : graphes

Mathématiques; Graphes; Tle générale; Matrices : graphes

Graphe connexe.
On peut par exemple construire une chaîne fermée de longueur 3 en reliant A à B, puis B à C, puis de nouveau C à A.

Graphe non connexe.
On peut par exemple construire une chaîne de longueur 2 de E à C.



Matrice d’adjacence

Chaque ligne et chaque colonne de la matrice d’adjacence représente un sommet du graphe. Pour un graphe d’ordre n, la matrice d’adjacence est une matrice carrée n×nn\times n​.


Dans un graphe non orienté, la valeur du coefficient ai,ja_{i,j}​ de la matrice est 1 si le sommet II​ est adjacent au sommet jj​. Sinon, le coefficient est 0.

Sommet

A

B

C

Ligne/colonne

1

2


3

(010101010)\left(\begin{matrix}0&1&0\\1&0&1\\0&1&0\\\end{matrix}\right)​​
Mathématiques; Graphes; Tle générale; Matrices : graphes


Dans un graphe orienté, la valeur du coefficient ai,ja_{i,j} de la matrice est 1 si une arête part du sommet II (ligne) et va vers le sommet jj (colonne). Sinon, le coefficient est 0.


Exemple

Sommet

A

B

C

Ligne/colonne

1

2

3

(011010100)\left(\begin{matrix}0&1&1\\0&1&0\\1&0&0\\\end{matrix}\right)​​

Mathématiques; Graphes; Tle générale; Matrices : graphes


Note : Dans le cas d’un graphe non orienté, la matrice adjacente est symétrique, c’est-à-dire que le coefficient ai,ja_{i,j} est toujours égal au coefficient aj,ia_{j,i}. Cependant, dans un graphe orienté, il est possible que les deux coefficients ne soient pas égaux.



Mathématiques; Graphes; Tle générale; Matrices : graphes




Foire aux questions (FAQ)

FAQs

  • Question : Qu'est-ce qu'un graphe complet ?

    Réponse : Un graphe est complet lorsque chacun de ses sommets est relié à tous les autres.

  • Question : Quel est le degré d'un sommet ?

    Réponse : Le degré d’un sommet est le nombre d’arrêtes qui le relient aux autres sommets.

  • Question : Qu'est-ce qu'un graphe ?

    Réponse : Un graphe est un ensemble fini d’éléments (les points), appelé sommets, reliés entre eux par des arêtes (les segments).

Théorie

Exercices

Protection des données

Nous et des tiers, tels que nos partenaires publicitaires et nos prestataires de services, utilisons des cookies et des technologies similaires pour fournir nos services, aider à personnaliser le contenu et mesurer les annonces. En cliquant sur "Accepter les cookies" ou en autorisant uniquement le cookie nécessaire via "Seulement le nécessaire", tu acceptes cette pratique (pour en savoir plus, consulte notre Politique de confidentialité). Politique de confidentialité