Coloration d'un graphe

 Publié le April 14, 2024  |  10 minutes  |  2115 mots  |  David Latreyte

L’objectif de cette séance est de découvrir comment colorier chaque sommet d’un graphe à l’aide d’un algorithme glouton. Colorier un graphe signifie associer une couleur à chacun de ses sommets de façon à ce que deux sommets liés par une arête n’aient pas la même couleur (deux sommets non adjacents peuvent avoir la même couleur). Colorier un graphe avec un nombre minimal de couleurs est un problème difficile mais l’utilisation d’un algorithme glouton permet de résoudre le problème, au prix d’un nombre de couleurs qui n’est pas toujours minimal. [Lire]
Graphe  Structure de données 

Représentation d'un graphe en informatique

 Publié le March 19, 2024  |  10 minutes  |  1951 mots  |  David Latreyte

Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d’adjacence (ou sommet-sommet), listes des voisins, des successeurs ou des prédécesseurs. Lors de cette séance nous allons écrire les classes réalisant ces implémentations. Structure de graphe basée sur une liste d’adjacence Écrire le code de la méthode __init__ de la classe Sommet dont la spécification est : 1 2 3 4 def __init__(self: Sommet, val: str) -> None: """ Initialisation d'un sommet. [Lire]
Graphe  Structure de données 

Parcours en profondeur : écriture du code en Python

 Publié le May 6, 2021  |  6 minutes  |  1168 mots  |  David Latreyte

Écriture d’une classe Graphe L’objectif de cette partie est l’écriture du code modélisant un graphe orienté. La représentation choisie est celle d’un dictionnaire de successeurs (en cours et dans le document 15,2 on a étudié les représentations par des matrice et liste de successeurs). La représentation par un dictionnaire de successeurs présente de nombreux avantages. Par exemple, les sommets peuvent être des entiers ou des chaînes de caractères quelconques ; La complexité de la liste des successeurs est directement proportionnelle au nombre de successeurs pour un sommet donné. [Lire]
Graphe  Structure de données 

Représentation d'un graphe en informatique

 Publié le April 22, 2021  |  7 minutes  |  1461 mots  |  David Latreyte

Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d’adjacence (ou sommet-sommet), listes des voisins, des successeurs ou des prédécesseurs. Lors de cette séance nous allons écrire les classes réalisant ces implémentations. Matrice sommet-sommet Écrire le code de la classe GrapheM qui implémente une matrice sommet-sommet. La spécification du constructeur de la classe est : 1 2 3 4 def __init__(self: GrapheM, mat: List[List[int]]) -> None: """ Constructeur de la classe. [Lire]
Graphe  Structure de données 

Les graphes

 Publié le April 20, 2021  |  1 minutes  |  196 mots  |  David Latreyte

Au programme de la partie « Structures de données » Contenus Capacités attendues Commentaires Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés. - Modéliser des situations sous forme de graphes. - Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs. - Passer d’une représentation à une autre. On s’appuie sur des exemples comme le réseau routier, le réseau électrique, internet, les réseaux sociaux. [Lire]
Graphe  Structure de données