madamasterclass.com
-
Connexion
Connexion
Exploration des algorithmes sur les graphes
Les algorithmes sur les graphes constituent des outils fondamentaux pour explorer et analyser des structures complexes. Ce cours vous guidera à travers divers algorithmes graphiques en utilisant le langage de programmation Python, en mettant l'accent sur leur application pratique.
Avant de plonger dans les algorithmes, il est essentiel de maîtriser les différentes méthodes de représentation des graphes. Nous examinerons la liste d'adjacence et la matrice d'adjacence, deux approches courantes en Python, pour comprendre comment elles influencent l'efficacité des algorithmes.
Les algorithmes de parcours, tels que la recherche en profondeur (DFS) et la recherche en largeur (BFS), sont cruciaux pour explorer la structure des graphes. Nous discuterons des applications pratiques de ces algorithmes, ainsi que des défis qu'ils peuvent résoudre.
Ce module couvre des algorithmes classiques, notamment :
Nous aborderons également les algorithmes de flot, en particulier l'algorithme d'Edmonds-Karp, qui permet de résoudre des problèmes complexes de flux dans les graphes, illustrant ainsi leur importance dans des applications réelles.
Les algorithmes sur les graphes jouent un rôle clé dans l'informatique et l'optimisation. Ce cours offre une exploration approfondie et pratique de ces algorithmes à travers des exemples concrets en Python, préparant ainsi les apprenants à résoudre des problèmes complexes dans le domaine.
La représentation des graphes est une étape cruciale pour manipuler ces structures de données complexes. En Python, deux méthodes couramment utilisées sont la liste d'adjacence et la matrice d'adjacence.
La liste d'adjacence est une représentation flexible où chaque nœud est associé à une liste de ses voisins. Cela économise de l'espace en ne stockant que les arêtes présentes.
Éducation
{
'A': ['B', 'D'],
'B': ['A', 'C'],
'C': ['B', 'D'],
'D': ['A', 'C']
}
La matrice d'adjacence est une matrice carrée où chaque ligne et colonne représentent un nœud. Les valeurs indiquent la présence ou l'absence d'arêtes entre les nœuds.
A B C D
A 0 1 0 1
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0
Dans cette matrice, un '1' à la position (i, j) indique une arête entre les nœuds i et j.
La liste d'adjacence est efficace pour les graphes creux, tandis que la matrice d'adjacence est adaptée aux graphes denses. Le choix dépend de la structure du graphe et des opérations à effectuer.
Comprendre les différentes façons de représenter les graphes est fondamental pour travailler efficacement avec ces structures de données. Les choix de représentation dépendent des caractéristiques du graphe et des besoins spécifiques de l'algorithme ou de l'application.
Le parcours de graphes est une opération fondamentale qui permet d'explorer la structure d'un graphe. En Python, deux algorithmes couramment utilisés sont la Recherche en Profondeur (DFS) et la Recherche en Largeur (BFS).
La recherche en profondeur explore aussi loin que possible le long d'une branche avant de revenir en arrière. C'est une approche récursive qui visite chaque nœud et explore ses voisins de manière récursive.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Exemple d'utilisation
dfs(graph, 'A')
La recherche en largeur explore tous les voisins d'un nœud avant de passer aux voisins de ses voisins. Elle utilise une file pour maintenir l'ordre des nœuds à explorer.
def bfs(graph, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Exemple d'utilisation
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
Les parcours de graphes sont utilisés pour résoudre divers problèmes tels que la détection de cycles, la recherche de chemins, la connectivité, et bien d'autres.
Les algorithmes de parcours de graphes sont essentiels pour comprendre la connectivité et la structure des graphes. Le choix entre DFS et BFS dépend des exigences spécifiques du problème.
Sommaire
L'algorithme de Dijkstra est utilisé pour trouver le plus court chemin entre un nœud source et tous les autres nœuds d'un graphe pondéré. Il fonctionne de manière efficace en utilisant une file de priorité pour sélectionner les nœuds à explorer en fonction de leur coût actuel.
Principe de fonctionnement
L'algorithme maintient un ensemble de distances minimales connues à partir du nœud source jusqu'à chaque nœud du graphe. À chaque étape, il sélectionne le nœud avec la distance minimale non encore explorée, puis met à jour les distances de ses voisins.
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
visited = []
for _ in range(len(graph)):
min_vertex = None
for vertex in distances:
if vertex not in visited:
if min_vertex is None or distances[vertex] < distances[min_vertex]:
min_vertex = vertex
visited.append(min_vertex)
for neighbor, weight in graph[min_vertex].items():
if neighbor not in visited:
new_distance = distances[min_vertex] + weight
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
return distances
# Exemple d'utilisation
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))
Exemple
Considérons le graphe pondéré suivant :
{
'A': {'B': 2, 'D': 5},
'B': {'A': 2, 'C': 4},
'C': {'B': 4, 'D': 1},
'D': {'A': 5, 'C': 1}
}
Si on applique l'algorithme de Dijkstra à partir du nœud 'A', on obtient les distances minimales suivantes :
{
'A': 0,
'B': 2,
'C': 5,
'D': 5
}
Cela signifie que le plus court chemin de 'A' à 'B' a une distance de 2, de 'A' à 'C' a une distance de 5, et de 'A' à 'D' a une distance de 5.
Applications
Dijkstra est largement utilisé pour la planification de chemins, la gestion de réseaux de transport, et tout autre problème nécessitant la recherche du plus court chemin dans un graphe pondéré.
L'algorithme de Bellman-Ford est utilisé pour trouver les plus courts chemins dans un graphe pondéré, même en présence de poids négatifs. Contrairement à Dijkstra, il peut gérer les poids négatifs, mais il a une complexité temporelle plus élevée.
Principe de Fonctionnement
L'algorithme fonctionne en itérant sur toutes les arêtes du graphe à plusieurs reprises, en mettant à jour les distances des nœuds. Il effectue ces itérations jusqu'à ce que plus aucune amélioration n'ait lieu, assurant ainsi la convergence vers les plus courts chemins.
def bellman_ford(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
for _ in range(len(graph) - 1):
for vertex in graph:
for neighbor, weight in graph[vertex].items():
if distances[vertex] + weight < distances[neighbor]:
distances[neighbor] = distances[vertex] + weight
return distances
# Exemple d'utilisation
graph = {
'A': {'B': 1, 'C': 4},
'B': {'C': -3, 'D': 2},
'C': {},
'D': {'A': -1}
}
print(bellman_ford(graph, 'A'))
Gestion des poids négatifs
Bellman-Ford peut détecter la présence de cycles de poids négatif dans le graphe. Si, après toutes les itérations, une amélioration est encore possible, cela indique la présence d'un cycle de poids négatif.
Exemple
Considérons le graphe pondéré suivant :
{
'A': {'B': -1, 'C': 4},
'B': {'C': 3, 'D': 2, 'E': 2},
'C': {},
'D': {'B': 1, 'C': 5},
'E': {'D': -3}
}
En appliquant Bellman-Ford à partir du nœud 'A', on obtient les distances minimales suivantes :
{
'A': 0,
'B': -1,
'C': 2,
'D': -2,
'E': 1
}
Applications
Bellman-Ford est utilisé dans des scénarios où la présence de poids négatifs est possible, comme les réseaux de coûts, les chemins dans des environnements dynamiques, et la détection de cycles de poids négatif.
L'algorithme de Kruskal est utilisé pour trouver un arbre couvrant minimal dans un graphe non orienté pondéré. Cet arbre couvrant connecte tous les nœuds du graphe avec un poids total minimum.
Principe de fonctionnement
L'algorithme de Kruskal fonctionne en triant toutes les arêtes du graphe par poids croissant, puis en les ajoutant progressivement à l'arbre couvrant minimal tout en évitant la formation de cycles. Il utilise une structure de données de disjoint sets (ensemble disjoint) pour suivre les composantes connexes du graphe.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
if self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
elif self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
def kruskal(graph):
edges = sorted(graph['edges'], key=lambda x: x[2])
uf = UnionFind(len(graph['vertices']))
mst = []
for u, v, weight in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, weight))
return mst
# Exemple d'utilisation
graph = {
'vertices': [0, 1, 2, 3],
'edges': [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
}
print(kruskal(graph))
Exemple
Considérons le graphe pondéré suivant :
{
'A': {'B': 2, 'D': 5},
'B': {'A': 2, 'C': 4},
'C': {'B': 4, 'D': 1},
'D': {'A': 5, 'C': 1}
}
En appliquant Kruskal, on obtient l'arbre couvrant minimal :
[('C', 'D', 1), ('B', 'C', 4), ('A', 'B', 2)]
Applications
Kruskal est utilisé dans des domaines tels que la conception de réseaux, la planification de câblage, et toute situation nécessitant une connexion minimale avec un coût global minimal.
L'algorithme de Prim est utilisé pour trouver un arbre couvrant minimal dans un graphe non orienté pondéré. Cet arbre couvrant connecte tous les nœuds du graphe avec un poids total minimum.
Principe de fonctionnement
L'algorithme de Prim commence par choisir un nœud initial, puis ajoute itérativement l'arête la plus légère connectant un nœud déjà inclus à un nœud hors de l'arbre couvrant minimal en cours de construction. Cela garantit qu'à chaque étape, l'arête ajoutée a le poids minimum parmi toutes les arêtes connectant l'arbre aux nœuds extérieurs.
def prim(graph, start):
mst = []
visited = {start}
edges = [(weight, start, to) for to, weight in graph[start].items()]
while edges:
edges.sort()
weight, frm, to = edges.pop(0)
if to not in visited:
visited.add(to)
mst.append((frm, to, weight))
for to_next, weight in graph[to].items():
if to_next not in visited:
edges.append((weight, to, to_next))
return mst
# Exemple d'utilisation
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(prim(graph, 'A'))
Exemple
Considérons le graphe pondéré suivant :
{
'A': {'B': 2, 'D': 5},
'B': {'A': 2, 'C': 4},
'C': {'B': 4, 'D': 1},
'D': {'A': 5, 'C': 1}
}
En appliquant Prim à partir du nœud 'A', on obtient l'arbre couvrant minimal :
[('A', 'B', 2), ('B', 'C', 4), ('C', 'D', 1)]
Applications
Prim est utilisé dans des domaines tels que la conception de réseaux, la planification de câblage, et toute situation nécessitant une connexion minimale avec un coût global minimal.
Ces algorithmes classiques sont fondamentaux pour résoudre divers problèmes liés aux graphes, tels que la recherche des plus courts chemins ou la création d'arbres couvrants minimaux. Le choix de l'algorithme dépend du contexte du problème et des caractéristiques du graphe.
Considérez le labyrinthe représenté sous forme de graphe :
laby = {1: [5, 2], 2: [1, 3, 6], 3: [2], 4: [8], 5: [1], 6: [2, 7], 7: [11, 6, 8], 8: [12, 7, 4], 9: [10],
10: [11, 9, 14], 11: [7, 10], 12: [8], 13: [14], 14: [13, 15, 10], 15: [16, 14], 16: [15]}
Implémentez une fonction parcours_profondeur(graphe, départ) qui effectue un parcours en profondeur du labyrinthe à partir du sommet de départ et renvoie la liste des sommets visités dans l'ordre.
def parcours_profondeur(graphe, départ):
pile = [départ]
visités = []
while pile:
sommet = pile.pop()
if sommet not in visités:
visités.append(sommet)
voisins = graphe[sommet]
pile.extend(voisins)
return visités
# Exemple d'utilisation
parcours = parcours_profondeur(laby, 1)
print(parcours)
# Résultat :
[1, 2, 3, 6, 7, 11, 10, 9, 14, 15, 16, 13, 4, 8, 12, 5]
Utilisez la fonction parcours_profondeur que vous avez implémentée pour trouver un chemin entre deux sommets du labyrinthe. Par exemple, recherchez un chemin entre le sommet 1 et le sommet 16.
def recherche_chemin(graphe, départ, arrivée):
pile = [(départ, [départ])]
while pile:
sommet, chemin = pile.pop()
if sommet == arrivée:
return chemin
voisins = graphe[sommet]
for voisin in voisins:
if voisin not in chemin:
pile.append((voisin, chemin + [voisin]))
return None
# Exemple d'utilisation
chemin = recherche_chemin(laby, 1, 16)
print(chemin)
# Résultat :
[1, 2, 3, 6, 7, 11, 10, 14, 13, 15, 16]
ⓘ Si un chemin existe entre le sommet de départ et le sommet d'arrivée, la fonction renvoie la liste des sommets constituant le chemin. Sinon, elle renvoie None.
Considérez le graphe représentant un réseau social avec les relations d'amitié suivantes :
graph = {
'Alice': ['Bob', 'Charlie'],
'Bob': ['Alice', 'Dave'],
'Charlie': ['Alice', 'Eve'],
'Dave': ['Bob'],
'Eve': ['Charlie', 'Frank'],
'Frank': ['Eve']
}Implémentez une fonction parcours_profondeur(graphe, départ) qui réalise un parcours en profondeur du graphe à partir du sommet de départ et renvoie la liste des sommets visités dans l'ordre.
def parcours_profondeur(graphe, départ):
pile = [départ]
visités = []
while pile:
sommet = pile.pop()
if sommet not in visités:
visités.append(sommet)
voisins = graphe[sommet]
pile.extend(voisins)
return visités
# Exemple d'utilisation
parcours = parcours_profondeur(graph, 'Alice')
print(parcours)
# Résultat :
['Alice', 'Charlie', 'Eve', 'Frank', 'Bob', 'Dave']
Utilisez la fonction parcours_profondeur que vous avez implémentée pour trouver un chemin entre deux sommets du graphe. Par exemple, recherchez un chemin entre 'Alice' et 'Frank'.
def recherche_chemin(graphe, départ, arrivée):
pile = [(départ, [départ])]
while pile:
sommet, chemin = pile.pop()
if sommet == arrivée:
return chemin
voisins = graphe[sommet]
for voisin in voisins:
if voisin not in chemin:
pile.append((voisin, chemin + [voisin]))
return None
# Exemple d'utilisation
chemin = recherche_chemin(graph, 'Alice', 'Frank')
print(chemin)
# Résultat :
['Alice', 'Charlie', 'Eve', 'Frank']
ⓘ Si un chemin existe entre le sommet de départ et le sommet d'arrivée, la fonction renvoie la liste des sommets constituant le chemin. Sinon, elle renvoie None.
Considérez le graphe représentant un réseau social avec les relations d'amitié suivantes :
graph = {
'Alice': ['Bob', 'Charlie'],
'Bob': ['Alice', 'Dave'],
'Charlie': ['Alice', 'Eve'],
'Dave': ['Bob'],
'Eve': ['Charlie', 'Frank'],
'Frank': ['Eve']
}Implémentez une fonction parcours_largeur(graphe, départ) qui réalise un parcours en largeur du graphe à partir du sommet de départ et renvoie la liste des sommets visités dans l'ordre.
def parcours_largeur(graphe, départ):
file = [départ]
visités = []
index = 0
while index < len(file):
sommet = file[index]
if sommet not in visités:
visités.append(sommet)
voisins = graphe[sommet]
file.extend(voisins)
index += 1
return visités
# Exemple d'utilisation
parcours = parcours_largeur(graph, 'Alice')
print(parcours)
# Résultat :
['Alice', 'Bob', 'Charlie', 'Dave', 'Eve', 'Frank']
Considérez un réseau routier représenté par le graphe suivant :
reseau_routier = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B', 'E'],
'E': ['C', 'D', 'F'],
'F': ['E']
}Implémentez une fonction parcours_largeur(graphe, départ) qui réalise un parcours en largeur du réseau routier à partir du sommet de départ et renvoie la liste des villes visitées dans l'ordre.
def parcours_largeur(graphe, départ):
file = [départ]
visités = []
index = 0
while index < len(file):
ville = file[index]
if ville not in visités:
visités.append(ville)
voisines = graphe[ville]
file.extend(voisines)
index += 1
return visités
# Exemple d'utilisation
parcours = parcours_largeur(reseau_routier, 'A')
print(parcours)
# Résultat :
['A', 'B', 'C', 'D', 'E', 'F']
Imaginez que vous avez une structure d'arborescence de fichiers représentée par le graphe suivant :
arborescence = {
'C:': ['Program Files', 'Users'],
'Program Files': ['Python', 'Java'],
'Users': ['Alice', 'Bob'],
'Python': ['Scripts', 'Lib'],
'Java': ['jdk', 'eclipse'],
'Alice': [],
'Bob': [],
'Scripts': ['script1.py', 'script2.py'],
'Lib': ['module1.py', 'module2.py'],
'jdk': ['bin', 'lib'],
'eclipse': ['eclipse.exe'],
'bin': ['java.exe'],
'lib': ['library1.jar', 'library2.jar']
}Implémentez une fonction parcours_largeur(graphe, départ) qui effectue un parcours en largeur de l'arborescence des fichiers à partir du répertoire de départ et renvoie la liste des fichiers et répertoires visités dans l'ordre
def parcours_largeur(graphe, départ):
file = [départ]
visités = []
index = 0
while index < len(file):
élément = file[index]
if élément not in visités:
visités.append(élément)
voisins = graphe[élément]
file.extend(voisins)
index += 1
return visités
# Exemple d'utilisation
parcours = parcours_largeur(arborescence, 'C:')
print(parcours)
# Résultat :
['C:', 'Program Files', 'Users', 'Python','Scripts', 'Lib', 'Java', 'Alice', 'Bob', 'jdk', 'eclipse', 'bin', 'lib', 'script1.py', 'script2.py', 'module1.py', 'module2.py', 'eclipse.exe', 'java.exe', 'library1.jar', 'library2.jar']
Considérez le graphe suivant :
graphe = {
'A': [('B', 1), ('C', 3)],
'B': [('A', 1), ('C', 2), ('D', 4)],
'C': [('A', 3), ('B', 2), ('D', 5)],
'D': [('B', 4), ('C', 5)]
}Implémentez l'algorithme de Prim pour trouver l'arbre couvrant de poids minimum à partir du sommet A.
def prim(graphe, départ):
visités = set()
arbre = []
visités.add(départ)
arêtes = [(poids, départ, voisin) for voisin, poids in graphe[départ]]
while arêtes:
arêtes.sort()
poids, u, v = arêtes.pop(0)
if v not in visités:
visités.add(v)
arbre.append((u, v, poids))
for voisin, poids in graphe[v]:
if voisin not in visités:
arêtes.append((poids, v, voisin))
return arbre
# Exemple d'utilisation
arbre_couvrant = prim(graphe, 'A')
print(arbre_couvrant)
# Résultat :
[('A', 'B', 1), ('C', 'D', 2), ('A', 'C', 3)]
Considérez le réseau suivant :
reseau = {
'A': [('B', 4), ('C', 2)],
'B': [('A', 4), ('C', 5), ('D', 10)],
'C': [('A', 2), ('B', 5), ('D', 3), ('E', 8)],
'D': [('B', 10), ('C', 3), ('E', 7), ('F', 6)],
'E': [('C', 8), ('D', 7), ('F', 9)],
'F': [('D', 6), ('E', 9)]
}Implémentez l'algorithme de Prim pour trouver l'arbre couvrant de poids minimum à partir du sommet A.
def prim(graphe, départ):
visités = set()
arbre = []
visités.add(départ)
arêtes = [(poids, départ, voisin) for voisin, poids in graphe[départ]]
while arêtes:
arêtes.sort()
poids, u, v = arêtes.pop(0)
if v not in visités:
visités.add(v)
arbre.append((u, v, poids))
for voisin, poids in graphe[v]:
if voisin not in visités:
arêtes.append((poids, v, voisin))
return arbre
# Exemple d'utilisation
arbre_couvrant = prim(graphe, 'B')
print(arbre_couvrant)
# Résultat :
[('B', 'C', 3), ('B', 'D', 5)]
Considérez le graphe de routes suivant :
routes = {
'A': [('B', 2), ('C', 3)],
'B': [('A', 2), ('C', 1), ('D', 4)],
'C': [('A', 3), ('B', 1), ('D', 5), ('E', 6)],
'D': [('B', 4), ('C', 5), ('E', 2)],
'E': [('C', 6), ('D', 2)]
}Implémentez l'algorithme de Prim pour trouver l'arbre couvrant de poids minimum à partir du sommet B.
def prim(graphe, départ):
visités = set()
arbre = []
visités.add(départ)
arêtes = [(poids, départ, voisin) for voisin, poids in graphe[départ]]
while arêtes:
arêtes.sort()
poids, u, v = arêtes.pop(0)
if v not in visités:
visités.add(v)
arbre.append((u, v, poids))
for voisin, poids in graphe[v]:
if voisin not in visités:
arêtes.append((poids, v, voisin))
return arbre
# Exemple d'utilisation
arbre_couvrant = prim(graphe, 'C')
print(arbre_couvrant)
# Résultat :
[('C', 'B', 1), ('B', 'A', 2), ('C', 'D', 3)]
Considérez le graphe suivant :
graphe = {
'A': [('B', 7), ('C', 9), ('D', 14)],
'B': [('A', 7), ('C', 10), ('E', 15)],
'C': [('A', 9), ('B', 10), ('D', 2), ('E', 11)],
'D': [('A', 14), ('C', 2), ('E', 9), ('F', 9)],
'E': [('B', 15), ('C', 11), ('D', 9), ('F', 6)],
'F': [('D', 9), ('E', 6)]
}Appliquez l'algorithme de Prim à partir du sommet A et trouvez l'arbre couvrant de poids minimum.
def prim(graphe, départ):
arbre = []
visités = set([départ])
arêtes = [(poids, départ, voisin) for voisin, poids in graphe[départ]]
while arêtes:
arêtes.sort()
poids, u, v = arêtes.pop(0)
if v not in visités:
visités.add(v)
arbre.append((u, v, poids))
for voisin, poids in graphe[v]:
if voisin not in visités:
arêtes.append((poids, v, voisin))
return arbre
# Exemple d'utilisation
arbre_couvrant = prim(graphe, 'A')
print(arbre_couvrant)
# Résultat :
[('A', 'C', 9), ('C', 'D', 2), ('D', 'E', 9), ('E', 'F', 6)]
Considérez le graphe suivant avec 8 sommets (A, B, C, D, E, F, G, H) et les arêtes suivantes :
• (A, B, 4) • (A, C, 1) • (A, D, 3) • (B, C, 2) • (B, E, 5) • (C, D, 6) • (C, F, 8) • (D, E, 7)
• (E, F, 3) • (E, G, 9) • (F, H, 2) • (G, H, 4)
1. Appliquez l'algorithme de Prim en commençant par le sommet A.
2. Trouvez l'arbre couvrant de poids minimum et calculez son poids total.
Considérez le graphe suivant avec 7 sommets (A, B, C, D, E, F, G) et les arêtes suivantes :
• (A, B, 10) • (A, C, 6) • (B, C, 4) • (B, D, 8) • (C, D, 2) • (C, E, 1) • (D, F, 5) • (E, F, 3) • (E, G, 7)
1. Appliquez l'algorithme de Prim en commençant par le sommet C.
2. Trouvez l'arbre couvrant de poids minimum et calculez son poids total.
Une ville souhaite construire un réseau de distribution d'eau pour relier plusieurs quartiers. Les quartiers sont représentés par des sommets, et les coûts de construction des conduites entre les quartiers sont représentés par les arêtes.
• (A, B, 3) • (A, C, 1) • (B, C, 5) • (B, D, 2) • (C, D, 4) • (C, E, 6)
1. Appliquez l'algorithme de Prim en commençant par le quartier A.
2. Trouvez l'arbre couvrant de poids minimum et calculez le coût total de construction.
Une compagnie d'électricité doit établir un réseau pour fournir de l'électricité à plusieurs stations. Les stations sont représentées par des sommets, et les coûts d'installation des lignes électriques entre les stations sont les arêtes.
• (A, B, 8) • (A, C, 3) • (B, C, 4) • (B, D, 6) • (C, D, 2) • (C, E, 5) • (D, E, 7)
1. Appliquez l'algorithme de Prim en commençant par la station A.
2. Trouvez l'arbre couvrant de poids minimum et calculez le coût total d'installation.
Une municipalité souhaite établir un réseau routier pour relier plusieurs localités. Les localités sont représentées par des sommets, et les coûts de construction des routes entre les localités sont les arêtes.
• (A, B, 5) • (A, C, 2) • (B, C, 3) • (B, D, 6) • (C, D, 4) • (C, E, 7) • (D, E, 1)
1. Appliquez l'algorithme de Prim en commençant par la localité A.
2. Trouvez l'arbre couvrant de poids minimum et calculez le coût total de construction.
Les mathématiques ont souvent la réputation d'être une discipline austère et difficile, mais ...
Read more.Plongez dans l'univers fascinant des suites numériques, où chaque terme révèle des patterns surprenants et des applications pratiques dans les mathématiques et au-delà.
Read more.Découvrez comment les fonctions tissent des liens entre les nombres et les concepts, transformant des idées abstraites en outils puissants pour résoudre des problèmes du quotidien.
Read more.
Abonnez-vous maintenant et recevez notre newsletter hebdomadaire avec des matériaux éducatifs, de nouveaux cours, des articles intéressants, des livres populaires et bien plus encore !
