Degré d’un sommet
rapelle : Dans un graphe non orienté, le degré d’un sommet \(v\), noté \(\deg(v)\), est le nombre d’arêtes incidentes à \(v\). Dans un graphe orienté, on distingue le degré sortant \(\deg^+(v)\) (nombre d’arcs issus de \(v\)) et le degré entrant \(\deg^-(v)\) (nombre d’arcs arrivant en \(v\)).
En termes de matrices :
- pour un graphe orienté, \(\deg^+(x_i) = \sum_j a_{ij}\), \(\deg^-(x_j) = \sum_i a_{ij}\) ;
- pour un graphe non orienté, \(\deg(x_i) = \sum_j a_{ij}\) (la matrice étant symétrique).
On peut calculer facilement les degrés avec NumPy et une matrice d’adjacence :
import numpy as np
A = np.array([[0, 1, 1], [0, 0, 1], [0, 0, 0]])
out_deg = A.sum(axis=1) # degrés sortants
in_deg = A.sum(axis=0) # degrés entrants
m = A.sum() # nombre d'arcs
La quantité \(\delta(G) = \min_v (deg(v))\) est appelée degré minimal du graphe et donne une borne supérieure naturelle à la connectivité (on ne peut pas avoir une connectivité strictement supérieure au degré minimal). Dit autrement c’est le plus petit nombre de sommets à enlever pour rendre le graphe non connecté (ou réduire à un seul sommet).
Exemple : si un sommet n’a que 3 voisins, enlever ces 3 sommets suffit à l’isoler; on ne peut donc pas demander que le graphe reste connecté après suppression de plus de 3 sommets.
Parcours et marches
Un parcours est une suite d’arêtes reliant des sommets. Selon les contraintes, on distingue :
- Élémentaire : aucun sommet n’est parcouru deux fois.
- Simple : aucune arête n’est parcourue deux fois (les sommets peuvent se répéter).
- Hamiltonien : chaque sommet est parcouru exactement une fois.
- https://mathworld.wolfram.com/HamiltonianGraph.html
- Pré-Hamiltonien : chaque sommet est parcouru au moins une fois, sans nécessairement former un cycle.
- https://mathworld.wolfram.com/AlmostHamiltonianGraph.html
- Eulerien : chaque arête est parcourue exactement une fois et le parcours forme un cycle ; tous les sommets ont un degré pair.
- https://mathworld.wolfram.com/EulerianCycle.html
- https://reference.wolfram.com/language/ref/FindEulerianCycle.html
- Pré-Eulerien (ou chinois) : chaque arête est parcourue au moins une fois ; existe si 0 ou 2 sommets sont impairs (la chaîne commence à un impair et finit à l’autre).
On appellera marche (walk) toute suite de sommets tel que chaque sommet est relié au suivant par une arête, sans interdire les répétitions. La longueur d’un chemin ou d’une marche est le nombre d’arêtes qui le composent.
- Soit $A$ la matrice d’adjacence du graphe.
- Pour tout $k ≥ 1$, le coefficient $(i,j)$ de $A^k$ est égal au nombre de marches de longueur $k$
- reliant le sommet $i$ au sommet $j$.
Explication puissance de $A^k$
L’idée vient directement de la définition du produit matriciel : chaque multiplication « recolle » des pas de longueur 1 pour former des chemins plus longs.
Cas $k = 2$ : $A^2$
Soit la matrice d’adjacence $A = (a_{ij})$, avec $a_{ij} = 1$ s’il y a un arc $i \to j$, $0$ sinon.
Le coefficient $(i,j)$ de $A^2$ est :
$$ (A^2)_{ij} = \sum_m a_{i m}, a_{m j} $$
Chaque terme $a_{i m} a_{m j}$ vaut 1 uniquement s’il y a à la fois un arc $i \to m$ et un arc $m \to j$. Donc, pour chaque sommet intermédiaire $m$, ce produit compte un chemin de longueur 2 : $i \to m \to j$. La somme sur tous les $m$ donne le nombre total de chemins (plus précisément de marches / pas) de longueur 2 entre $i$ et $j$. (voir bimsa)
Cas général \(k\)
On répète exactement le même raisonnement par récurrence :
- $A$ compte les chemins de longueur 1.
- Si $A^{k}$ compte les chemins de longueur $k$, alors $A^{k+1} = A^{k} \cdot A$ recolle un chemin de longueur $k$ (de $i$ à un sommet intermédiaire $m$ avec un arc de longueur 1 (de $m$ à $j$), donc $(A^{k+1})_{ij}$ compte tous les chemins de longueur $k+1$ de $i$ à $j$.
On obtient ainsi le résultat général : $(A^k)_{ij}$ est le nombre de marches (walks) de longueur $k$ entre $i$ et $j$.
Attention : ce sont des pas, donc on a le droit de repasser plusieurs fois par le même sommet ou la même arête.
Petit exemple concret
Prends le graphe orienté : \(1 \to 2\), \(2 \to 3\), \(1 \to 3\).
\[ A = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix} \]
Calcule \(A^2\) (à la main ou en Python) : on obtient
\[ A^2 = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \]
- Le coefficient \((1,3)\) vaut 1 : il existe exactement un chemin de longueur 2 de 1 à 3, à savoir \(1 \to 2 \to 3\).
- Les autres entrées sont 0 : il n’existe aucun chemin de longueur 2 pour les autres paires de sommets.
Calcule \(A^3\) (à la main ou en Python) : on obtient
\[ A^3 = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \]
- Il n’existe pas de chemin de longueur 3 ou plus
Connexité
Intuitivement, un graphe est connecté si l’on peut aller de n’importe quel sommet à n’importe quel autre en suivant les arêtes. Plus formellement :
- pour un graphe non orienté, on parle de connexité : il existe un chemin entre toute paire de sommets ;
- pour un graphe orienté, on distingue
- fortement connexe : pour tout couple \((u,v)\), il existe un chemin dirigé de \(u\) vers \(v\) et de \(v\) vers \(u\) ;
- faiblement connexe : si l’on oublie l’orientation des arcs, le graphe sous-jacent non orienté est connecté.
On peut caractériser la connexité via des composantes connexes (non orienté) ou composantes fortement connexes (orienté) :
- un graphe non orienté est connecté s’il ne possède qu’une seule composante connexe ;
- un graphe orienté est fortement connexe s’il ne possède qu’une seule composante fortement connexe.
Sur le plan plus algébrique, la connexité se reflète dans les matrices associées. Par exemple, pour un graphe non orienté, le nombre de composantes connexes est égal à la multiplicité de la valeur propre \(0\) de la matrice de Laplacien (voir plus bas). (ressource : math.uchicago)
Eulerien
- Un graphe simple et connexe est dit Eulerien si et seulement si tous ses sommets ont un degré pair.
- Dans ce cas, il existe un cycle eulérien, c’est-à-dire un cycle qui passe une et une seule fois par chaque arête du graphe.
- Si dessous deux exemples : Couleur verte pour les sommets pairs.
Pré-Eulerien
- Un graphe pré-Eulerien (ou semi-Eulerien) connexe ou encore multigraphe admet une chaine eulerienne
- Si et seulement si le nombre de degret impaire est 0 :
- ou 2 (pre eulerien) : La chaîne eulérienne commence à un sommet impair (A) et se termine à l’autre (D) :
Graphe non orienté
Connexe (positif)
Non connexe (négatif)
Graphe orienté
Fortement connexe (positif)
Faiblement connexe mais pas fortement (positif/faiblement)
Ni fortement ni faiblement connexe
Graphes bipartis
Un graphe non orienté \(G = (V, E)\) est biparti si l’ensemble des sommets peut être partitionné en deux sous-ensembles \(V_1\) et \(V_2\) tels qu’aucune arête n’a ses deux extrémités dans le même sous-ensemble. Autrement dit, toutes les arêtes relient un sommet de \(V_1\) à un sommet de \(V_2\).
On dispose de plusieurs caractérisations équivalentes :
- \(G\) est biparti si et seulement s’il n’admet aucun cycle de longueur impaire.
- \(G\) est biparti si et seulement si son graphe est 2-colorable (coloration des sommets avec 2 couleurs, aucune arête n’ayant deux extrémités de même couleur) (voir le cours sur Sémiologie et cartographie ).
Au niveau matriciel, après avoir ordonné les sommets de sorte que ceux de \(V_1\) viennent avant ceux de \(V_2\), la matrice d’adjacence d’un graphe biparti non orienté s’écrit :
\[ A = \begin{pmatrix} 0_{r,r} & B \\ B^{\mathsf T} & 0_{s,s} \end{pmatrix}, \]
où \(r = |V_1|\), \(s = |V_2|\) et \(B\) est la bi-matrice d’adjacence qui encode les connexions entre \(V_1\) et \(V_2\).
Cette structure a des conséquences spectrales importantes : le spectre de \(A\) est symétrique par rapport à \(0\), i.e. si \(\lambda\) est valeur propre, alors \(-\lambda\) l’est aussi (avec même multiplicité), on va approfondir juste apres.
En Python, on peut stocker un biparti par ses deux parties et une matrice \(B\) :
U = ["u1", "u2"] # première partie
V = ["v1", "v2", "v3"] # seconde partie
B = np.array([
[1, 0, 1], # u1 connecté à v1 et v3
[0, 1, 0] # u2 connecté à v2
])
Graphiquement :
Autre exemple
Graphes tripartis
Un graphe triparti est un graphe dont les sommets peuvent être divisés en trois ensembles disjoints (U, V, W), de sorte qu’aucune arête ne relie deux sommets du même ensemble. La plus part des reseaux de neuronnes simple (multi-layer perceptron) sont tripartis:
source stackexchange.com
Exemple simple
Soit le graphe suivant :
- \(U = \{u1, u2\}\)→ orange
- \(V = \{v1, v2\}\) → vert
- \(W = \{w1, w2\}\) → bleu
Graphe triparti complet
Un graphe triparti est un graphe dont les sommets peuvent être divisés en trois ensembles disjoints (U, V, W), de sorte qu’aucune arête ne relie deux sommets du même ensemble. La plus part des reseaux de neuronnes simple (multi-layer perceptron) sont tripartis:
source stackexchange.com
Graphe non complet triparti
- Similaire au graphe du dessus
- Certaines arêtes manquent, donc pas toutes les combinaisons entre \((U, V, W)\) sont présentes.
- On peut facilement colorer chaque ensemble pour visualiser qu’aucune arête ne relie deux sommets du même ensemble.
Voici une reformulation plus courte + un petit exemple Mermaid.
Fermeture transitive
Soit un graphe orienté \(G = (V, E)\). La fermeture transitive de \(G\), notée \(\widehat{G} = (V, \widehat{E})\), est le graphe qui possède les mêmes sommets que \(G\) et dans lequel on ajoute un arc \((x_i, x_j)\) dès qu’il existe au moins un chemin orienté de \(x_i\) vers \(x_j\) dans \(G\). On peut la (la fermeture) voir comme le graphe où on rend expllicites tous les arcs “déduits par transitivité” : si on peut aller de \(x_i\) à \(x_j\) en plusieurs étapes, on ajoute un arc direct \((x_i, x_j)\).
Graphe de départ \(G\) :
Dans \(G\), il existe un chemin \(A \to B \to C\), donc la fermeture transitive \(\widehat{G}\) ajoutera l’arc direct \(A \to C\).
Fermeture transitive \(\widehat{G}\) :
Ici, l’arc \(A \to C\) (en rouge) n’était pas dans le graphe initial, mais il apparaît dans la fermeture transitive car \(C\) est atteignable depuis \(A\) par un chemin orienté. youtube
Idem graphe non orientee:
Algorithme de fermeture
def transitive_closure(M):
M = np.array(M, dtype=int)
n = M.shape[0]
M_hat = M.copy()
p = 2
while True:
Mp = np.linalg.matrix_power(M, p)
N = ((M_hat > 0) | (Mp > 0)).astype(int)
# Si aucune nouvelle case à 1 n'est ajoutée, on s'arrête
if np.array_equal(N, M_hat):
break
M_hat = N
p += 1
return M_hat