Bases de la théorie des graphes et représentation
1. Concept et introduction
La théorie des graphes est une branche des mathématiques discrètes, une discipline qui étudie les graphes.
Un graphe est une structure mathématique utilisée pour modéliser des relations par paires entre des objets, composée de « nœuds » ou « sommets » (Vertex) et des « arêtes » (Edge) qui relient ces sommets.
Il convient de noter que l’ensemble des sommets d’un graphe ne peut pas être vide, mais l’ensemble des arêtes peut être vide. Un graphe peut être non orienté, ce qui signifie que les arêtes du graphe ne distinguent pas de direction lorsqu’elles relient des sommets. Sinon, le graphe est dit orienté. La figure de gauche ci-dessous est une structure typique de graphe non orienté, tandis que la figure de droite est un graphe orienté. Les graphes présentés dans ce chapitre sont tous des graphes non orientés.
Classification des graphes : graphes non pondérés et graphes pondérés. Si les arêtes reliant les nœuds ont des valeurs numériques associées, il s’agit d’un graphe pondéré ; sinon, il s’agit d’un graphe non pondéré.
Connectivité des graphes :En théorie des graphes, le graphe connexe repose sur le concept de connectivité. Dans un graphe non orienté G, s’il existe un chemin reliant le sommet i au sommet j (bien sûr, il doit aussi exister un chemin de j vers i), alors i et j sont dits connectés. Si G est un graphe orienté, alors toutes les arêtes du chemin reliant i et j doivent être dans la même direction. Si deux sommets quelconques du graphe sont connectés, le graphe est appelé graphe connexe. Si le graphe est orienté, il est appelé graphe fortement connexe (remarque : les chemins doivent exister dans les deux sens). La connectivité d’un graphe est une propriété fondamentale des graphes.
Graphe complet :Un graphe complet est un graphe simple non orienté dans lequel exactement une arête relie chaque paire de sommets distincts.
Boucle :Les points de départ et d’arrivée d’une arête sont des sommets.
Arête parallèle :Plusieurs arêtes existent entre deux sommets.
II. Notes d'applicabilité
Les graphes peuvent être utilisés pour modéliser de nombreux types de relations et processus dans les systèmes physiques, biologiques, sociaux et d'information, et de nombreux problèmes pratiques peuvent être représentés par des graphes. Par conséquent, la théorie des graphes est devenue un puissant outil mathématique pour de nombreuses disciplines telles que la recherche opérationnelle, la cybernétique, la théorie de l'information, la théorie des réseaux, la théorie des jeux, la physique, la chimie, la biologie, les sciences sociales, la linguistique et l'informatique. Lorsqu'on met l'accent sur son application aux systèmes du monde réel, un réseau est parfois défini comme un graphe dans lequel les relations entre des attributs (tels que des noms) sont associées sous la forme de nœuds et/ou d'arêtes.
3. Formes de représentation des graphes
Matrice d'adjacence :1 indique connecté, 0 indique non connecté.
Liste d'adjacence :Représente uniquement les informations sur les sommets connectés à un sommet
La liste d'adjacence convient pour représenter des graphes creux.
La matrice d'adjacence convient pour représenter des graphes denses.
Exemple de code Java
Téléchargement du paquet de code source :Télécharger
(1) Matrice d'adjacence
Code du fichier src/example/graph/DenseGraph.java :
/**
* Matrice d'adjacence
*/
public class DenseGraph {
// Nombre de nœuds
private int n;
// Nombre d'arêtes
private int m;
// Indique s'il s'agit d'un graphe orienté
private boolean directed;
// Données spécifiques du graphe
private boolean[][] g;
// constructeur
public DenseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g est initialisé comme une matrice booléenne n*n, chaque g[i][j] est false, ce qui indique qu'il n'y a pas d'arêtes
// false est la valeur par défaut des variables booléennes
g = new boolean[n][n];
}
// Renvoie le nombre de nœuds
public int V(){ return n;}
// Renvoie le nombre d'arêtes
public int E(){ return m;}
// Ajoute une arête au graphe
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) )
return;
g[v][w] = vrai;
if( !directed )
g[w][v] = vrai;
m ++;
}
// Vérifie s'il existe une arête de v à w dans le graphe
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
}
(2) Liste d'adjacence
src/example/graph/SparseGraph.java code du fichier :
import java.util.Vector;
/**
* Liste d'adjacence
*/
public class SparseGraph {
// Nombre de nœuds
private int n;
// Nombre d'arêtes
private int m;
// Indique s'il s'agit d'un graphe orienté
private boolean directed;
// Données spécifiques du graphe
private Vector<Integer>[] g;
// constructeur
public SparseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g est initialisé comme n vecteurs vides, ce qui signifie que chaque g[i] est vide, c'est-à-dire aucune arête
g = (Vector<Integer>[])new Vecteur[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
// Renvoie le nombre de nœuds
public int V(){ return n;}
// Renvoie le nombre d'arêtes
public int E(){ return m;}
// Ajoute une arête au graphe
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].ajoutez(w);
if( v != w && !directed )
g[w].ajoutez(v);
m ++;
}
// Vérifie s'il existe une arête de v à w dans le graphe
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
}