logoChat01.ai

rouvez L(G) d’une chaine de 4 nœuds. L(G) = 10/6 =...

Erstellt am: 17. Januar 2026

Beantwortet mit GPT-5.2 von Chat01

Frage

rouvez L(G) d’une chaine de 4 nœuds.
L(G) = 10/6 = 1.66 KIFHH JAT

Antwort

Pour une chaîne (path) de 4 nœuds : 1−2−3−41-2-3-4

  • Nombre de sommets : n=4n=4
  • Nombre d’arêtes : m=3m=3
  • Distances entre toutes les paires (6 paires au total) : d12=1, d13=2, d14=3, d23=1, d24=2, d34=1d_{12}=1,\ d_{13}=2,\ d_{14}=3,\ d_{23}=1,\ d_{24}=2,\ d_{34}=1 Somme : 1+2+3+1+2+1=101+2+3+1+2+1 = 10

Donc si L(G)L(G) est la distance moyenne :

L(G)=∑i<jd(i,j)(n2)=106=53≈1.666…L(G)=\frac{\sum_{i<j} d(i,j)}{\binom{n}{2}} =\frac{10}{6}=\frac{5}{3}\approx 1.666\ldots

✅ Conclusion : L(G)=10/6≈1,66L(G)=10/6 \approx 1{,}66 (ton résultat est correct).

Pour “KIFHH JAT” : ça ressemble à un texte chiffré (César/Vigenère, etc.). Si tu me dis le type de chiffrement ou la clé/décalage, je te le décode.

Frage

Cours6.pdf
Cours7.pdf
Cours8.pdf
Cours9.pdf

CE LES 4 COUR DONNE MOI DES QST PEUT DONNE LE PROF EN CONTROLE

Gedanke

All the files uploaded by the user have been fully loaded. Searching won't provide additional information.

Thought for 7s

Gedanke

Thought for 7s

Antwort

Voici des questions typiques que le prof peut donner en contrôle (basées sur Cours 6→9, Chapitre 2 : Optimisation de la Topologie).

Cours 6 — Modèle du réseau (canal sans fil, graphe, énergie, mobilité)

  1. Différences Ad hoc vs WSN (réseaux de capteurs) : citer 3 différences + 2 similarités. (Cours6.pdf)
  2. Définir le seuil de sensibilité β et la condition d’existence d’un lien radio entre uu et vv. (Cours6.pdf)
  3. Comparer les modèles de propagation : free-space vs two-ray (exposant en distance, conséquence sur la portée). (Cours6.pdf)
  4. Modèle log-distance : donner le rôle de l’exposant α\alpha et citer des valeurs typiques selon l’environnement. (Cours6.pdf)
  5. Définir le graphe de communication produit par une affectation de portée RARA (graphe orienté, condition (u,v)∈E(u,v)\in E). (Cours6.pdf)
  6. Lien bidirectionnel vs asymétrique + pourquoi c’est important. (Cours6.pdf)
  7. Définir “range assignment connectant” (fortement connexe). (Cours6.pdf)
  8. Énergie : définir le coût énergétique cost(RA)\text{cost}(RA) et expliquer le lien avec le modèle log-distance. (Cours6.pdf)
  9. Modèles de mobilité : expliquer RWP, Random Direction, Map-based, Group-based (principe + exemple d’usage). (Cours6.pdf)

Exercice probable (Cours 6)
10) On te donne des positions (ou distances) + un RA(u)RA(u). Construire le graphe orienté, repérer les liens symétriques/asymétriques, dire si c’est fortement connexe.

Cours 7 — Topology Control (définition, taxonomie, placement)

  1. Motivation énergie : montrer pourquoi multi-sauts courts < lien direct long (avec free-space). (Cours7.pdf)
  2. Définition exacte de “topology control” (coordination des portées pour propriétés globales + économie énergie). (Cours7.pdf)
  3. CTR (homogeneous) vs nonhomogeneous : expliquer et donner les 3 familles nonhomogènes (location/direction/neighbor-based). (Cours7.pdf)
  4. Où placer la couche Topology Control dans la pile protocolaire ? (entre routing et MAC selon Santi) + pourquoi. (Cours7.pdf)
  5. Interaction TC ↔ Routing : quand TC déclenche une mise à jour de routes ? et inversement. (Cours7.pdf)
  6. 802.11 RTS/CTS/ACK : expliquer la séquence et l’idée “overhearing” des voisins. (Cours7.pdf)
  7. Puissance et capacité réseau : expliquer l’exemple u ⁣→ ⁣vu\!\to\!v et w ⁣→ ⁣zw\!\to\!z (quand on réduit les portées, transmissions simultanées possibles). (Cours7.pdf)

Exercice probable (Cours 7)
8) On te donne 4 nœuds + distances d1,d2,d3d_1,d_2,d_3. Choisir rr pour permettre/empêcher les transmissions simultanées (concept capacité). (Cours7.pdf)

Cours 8 — CTR + Range Assignment (RA/SRA)

  1. Définir CTR : même portée pour tous, minimiser rr pour une propriété (souvent connectivité). (Cours8.pdf)
  2. Théorème (Santi 2005) : CTR(connectivité) = longueur de la plus grande arête de l’EMST. (Cours8.pdf)
  3. Pourquoi EMST/CTR est difficile en distribué ? (besoin connaissance globale/positions). (Cours8.pdf)
  4. Cas pessimiste sans positions : pourquoi CTR peut être L2L\sqrt{2} dans une région carrée. (Cours8.pdf)
  5. CTR probabiliste (réseaux denses) : expliquer l’idée “connected w.h.p.” et ce que ça répond comme questions. (Cours8.pdf)
  6. Range Assignment (RA) : définition + objectif (connectivité + minimiser coût énergie). (Cours8.pdf)
  7. RA NP-hard en 2D/3D (Kirousis 2000). (Cours8.pdf)
  8. Approx RA par MST : donner les 3 étapes + comment définir RAT(u)RA_T(u). (Cours8.pdf)
  9. Borne : cost(RAT)<2 cost(RAopt)\text{cost}(RA_T) < 2\,\text{cost}(RA_{opt}). (Cours8.pdf)
  10. SRA (Symmetric RA) : définir symétrie (liens bidirectionnels) + pourquoi on évite unidirectionnels (routing/MAC). (Cours8.pdf)
  11. SRA en 1D (sur une ligne) : donner l’algorithme optimal (extrémités + max voisin gauche/droit). (Cours8.pdf)

Exercices probables (Cours 8)
12) On te donne des points (ou un graphe complet pondéré) :

  • construire le MST, puis calculer RAT(u)RA_T(u) pour chaque nœud. (Cours8.pdf)
  1. Nœuds sur une ligne avec coordonnées : appliquer l’algo SRA 1D et donner les portées finales. (Cours8.pdf)

Cours 9 — Topology control distribué + protocole LMST

  1. Pourquoi les solutions centralisées sont mauvaises en ad hoc/WSN (ressources + tolérance aux pannes). (Cours9.pdf)
  2. 4 propriétés idéales d’un protocole TC : distribué, localisé, préserver connectivité + liens bidirectionnels, info “low-quality”. (Cours9.pdf)
  3. Qualité de l’info (high/medium/low) et relation avec économie d’énergie. (Cours9.pdf)
  4. LMST (Li-Hou-Sha 2003) : c’est quoi ? et quel type d’info il utilise (positions). (Cours9.pdf)
  5. Les phases de LMST :
  • beacon ID+position (max power),
  • MST local (Prim) + règle d’unicité,
  • voisinage NT(u)NT(u),
  • calcul puissance pour atteindre le plus loin,
  • option bidirectionnalité GLMST+G^+_{LMST} vs GLMST−G^-_{LMST}. (Cours9.pdf)
  1. Expliquer différence :
  • GLMST+G^+_{LMST} (on force symétrie → plus dense, plus de redondance),
  • GLMST−G^-_{LMST} (on supprime liens unidirectionnels → très creux). (Cours9.pdf)

Exercice très probable (Cours 9)
7) On te donne un max-power graph pondéré : appliquer LMST pour obtenir GLMST+G^+_{LMST} et GLMST−G^-_{LMST}. (C’est exactement le type d’exercice montré). (Cours9.pdf)

Si tu veux, envoie-moi une photo/énoncé de ton TD ou du dernier contrôle, et je te prépare une mini-série “contrôle blanc” (10 questions + corrigé).

Frage

Cours5.pdf

FAIT MOI L EXERCICE DE DERNIER PAGE

Gedanke

All the files uploaded by the user have been fully loaded. Searching won't provide additional information.

Thought for 9s

Python

python
import itertools, math, networkx as nx, pandas as pd
# define graph
edges = [
(1,2,5),(2,8,2),(2,9,3),(9,8,2),(1,7,3),
(7,6,3),(6,5,2),(5,4,2),(7,3,5),(7,4,5),(7,5,4),
(3,5,3),(3,6,5),(4,6,4),(4,3,2),(1,3,4)
]
G=nx.Graph()
G.add_weighted_edges_from(edges)
nodes=sorted(G.nodes())
nodes


[1, 2, 3, 4, 5, 6, 7, 8, 9]

Python

python
from heapq import heappush, heappop
def local_mst_edges(u):
    VN=set(G.neighbors(u))
    V=set(VN)|{u}
    # Prim starting from u
    inA={u}
    edges_mst=[]
    # heap items: (weight, outside_id, inside_id) ??? tie as described: compare endpoint outside A then inside
    heap=[]
    for v in VN:
        w=G[u][v]['weight']
        # outside=v, inside=u
        heappush(heap,(w, v, u, u, v))
    while heap and len(inA)<len(V):
        w, outside, inside, a,b = heappop(heap)
        if outside in inA and inside in inA: 
            continue
        # determine which is outside/inside now
        if a in inA and b not in inA:
            inside=a; outside=b
        elif b in inA and a not in inA:
            inside=b; outside=a
        else:
            continue
        # add edge
        inA.add(outside)
        edges_mst.append((inside,outside,w))
        # push new crossing edges
        for nbr in G.neighbors(outside):
            if nbr in V and nbr not in inA:
                ww=G[outside][nbr]['weight']
                # inside=outside, outside=nbr
                heappush(heap,(ww, nbr, outside, outside, nbr))
    return edges_mst

def NT(u):
    mst=local_mst_edges(u)
    nt=set()
    for a,b,w in mst:
        if a==u: nt.add(b)
        elif b==u: nt.add(a)
    return nt, mst

nts={}
msts={}
for u in nodes:
    nt,mst=NT(u)
    nts[u]=sorted(nt)
    msts[u]=mst
nts


{1: [2, 3, 7],
 2: [1, 8],
 3: [4],
 4: [3, 5],
 5: [4, 6],
 6: [5, 7],
 7: [1, 6],
 8: [2, 9],
 9: [8]}

Python

python
GL=nx.DiGraph()
for u,vs in nts.items():
    for v in vs:
        GL.add_edge(u,v,weight=G[u][v]['weight'])
# Determine bidirectional
bid=set()
uni=set()
for u,v in GL.edges():
    if GL.has_edge(v,u):
        bid.add((u,v))
    else:
        uni.add((u,v))
len(GL.edges()), uni


(17, {(1, 3)})

Python

python
def undirected_edges_from_digraph(D):
    s=set()
    for u,v in D.edges():
        s.add(tuple(sorted((u,v))))
    return sorted(s)
Gminus=GL.copy()
Gminus.remove_edge(1,3)
# For Gplus: add reverse of unidirectional edges
Gplus=GL.copy()
for u,v in uni:
    if not Gplus.has_edge(v,u):
        Gplus.add_edge(v,u,weight=G[u][v]['weight'])
und_plus=undirected_edges_from_digraph(Gplus)
und_minus=undirected_edges_from_digraph(Gminus)
und_plus, und_minus


([(1, 2), (1, 3), (1, 7), (2, 8), (3, 4), (4, 5), (5, 6), (6, 7), (8, 9)],
 [(1, 2), (1, 7), (2, 8), (3, 4), (4, 5), (5, 6), (6, 7), (8, 9)])

Gedanke

def undirected_edges_from_digraph(D): s=set() for u,v in D.edges(): s.add(tuple(sorted((u,v)))) return sorted(s) Gminus=GL.copy() Gminus.remove_edge(1,3)

For Gplus: add reverse of unidirectional edges

Gplus=GL.copy() for u,v in uni: if not Gplus.has_edge(v,u): Gplus.add_edge(v,u,weight=G[u][v]['weight']) und_plus=undirected_edges_from_digraph(Gplus) und_minus=undirected_edges_from_digraph(Gminus) und_plus, und_minus

([(1, 2), (1, 3), (1, 7), (2, 8), (3, 4), (4, 5), (5, 6), (6, 7), (8, 9)], [(1, 2), (1, 7), (2, 8), (3, 4), (4, 5), (5, 6), (6, 7), (8, 9)])

Thought for 1m 14s

Antwort

OK — l’exercice de la dernière page (LMST) de ton cours demande de trouver GLMST+G^+_{LMST} et GLMST−G^-_{LMST} à partir du max-power graph (liste des arêtes + poids) (Cours9.pdf).

1) Voisinage visible VN(u)VN(u) (dans le max-power graph)

À partir des arêtes données (Cours9.pdf) :

  • VN(1)={2,3,7}VN(1)=\{2,3,7\}
  • VN(2)={1,8,9}VN(2)=\{1,8,9\}
  • VN(3)={1,4,5,6,7}VN(3)=\{1,4,5,6,7\}
  • VN(4)={3,5,6,7}VN(4)=\{3,5,6,7\}
  • VN(5)={3,4,6,7}VN(5)=\{3,4,6,7\}
  • VN(6)={3,4,5,7}VN(6)=\{3,4,5,7\}
  • VN(7)={1,3,4,5,6}VN(7)=\{1,3,4,5,6\}
  • VN(8)={2,9}VN(8)=\{2,9\}
  • VN(9)={2,8}VN(9)=\{2,8\}

2) Construction LMST : NT(u)NT(u) (voisins gardés par chaque nœud)

Règle LMST : chaque nœud construit son MST local (Prim) puis garde les voisins directement reliés à lui dans ce MST :

NT(u)={v∈VN(u)∣(u,v)∈Tu}NT(u)=\{v\in VN(u)\mid (u,v)\in T_u\}

(Cours9.pdf)

Résultats :

  • NT(1)={2,3,7}NT(1)=\{2,3,7\} (comme dans la solution partielle) (Cours9.pdf)
  • NT(2)={1,8}NT(2)=\{1,8\}
  • NT(3)={4}NT(3)=\{4\} (comme dans la solution partielle) (Cours9.pdf)
  • NT(4)={3,5}NT(4)=\{3,5\}
  • NT(5)={4,6}NT(5)=\{4,6\}
  • NT(6)={5,7}NT(6)=\{5,7\}
  • NT(7)={1,6}NT(7)=\{1,6\}
  • NT(8)={2,9}NT(8)=\{2,9\}
  • NT(9)={8}NT(9)=\{8\}

Donc le graphe orienté GLMSTG_{LMST} contient toutes les arêtes u→vu\to v pour v∈NT(u)v\in NT(u). (Cours9.pdf)

3) Liens unidirectionnels → GLMST+G^+_{LMST} et GLMST−G^-_{LMST}

On vérifie les liens :

  • 1→31\to 3 existe (car 3∈NT(1)3\in NT(1)),
  • mais 3→13\to 1 n’existe pas (car NT(3)={4}NT(3)=\{4\}).
    Donc 1→31\to 3 est unidirectionnel (exactement l’exemple expliqué dans la page) (Cours9.pdf).

a) GLMST−G^-_{LMST} (technique 2) : on supprime les liens unidirectionnels

Donc on supprime 1→31\to 3.

Arêtes (en non-orienté / liens) de GLMST−G^-_{LMST} :

{(1,2),(1,7),(2,8),(8,9),(3,4),(4,5),(5,6),(6,7)}\{(1,2),(1,7),(2,8),(8,9),(3,4),(4,5),(5,6),(6,7)\}

b) GLMST+G^+_{LMST} (technique 1) : on rend bidirectionnels

Donc on ajoute 3→13\to 1 pour rendre 1↔31\leftrightarrow 3 bidirectionnel. (Cours9.pdf)

Liens (non-orientés) de GLMST+G^+_{LMST} :

{(1,2),(1,7),(1,3),(2,8),(8,9),(3,4),(4,5),(5,6),(6,7)}\{(1,2),(1,7),(1,3),(2,8),(8,9),(3,4),(4,5),(5,6),(6,7)\}

Si tu veux, je peux aussi te dessiner le graphe final (même à la main façon “corrigé”) en me disant si ton prof veut orienté (flèches) ou non-orienté (liens).

Frage

Nous voulons faire un résumé du chapitre 1 de notre cours. Remplir le tableau suivant
par :
 P_E (qui signifie « un algorithme polynomial existe pour trouver le chemin (ou
l’arbre) optimal»)
 P_D_E (qui signifie « il n’existe pas d’algorithme polynomial pour trouver le
chemin (ou l’arbre) optimal »)
Métrique
Type de
Routage
Délai Distance Coût de
location
Distance
avec
contrainte
de délai
Coût de
location
avec
contrainte
de délai
Unicast
Multicast
Broadcast THISSS

Antwort

Parfait, on remplit l’Exercice 2 (résumé du chapitre 1) exactement comme le prof l’attend.

👉 Règle clé du cours (Chapitre 1)

  • Sans contrainte de délai → il existe des algorithmes polynomiaux
  • Avec contrainte de délai → le problème devient NP-complet ⇒ pas d’algorithme polynomial connu
    (c’est explicitement dit dans la section Routage avec contrainte de délai)

Tableau complété

Type de routageDélaiDistanceCoût de locationDistance avec contrainte de délaiCoût de location avec contrainte de délai
UnicastP_EP_EP_EP_D_EP_D_E
MulticastP_EP_EP_EP_D_EP_D_E
BroadcastP_EP_EP_EP_D_EP_D_E

Justification rapide (à mémoriser pour le contrôle)

  • Unicast

    • Distance → plus court chemin (Dijkstra) → P_E
    • Délai → plus court chemin → P_E
    • Coût de location → plus court chemin → P_E
    • Avec contrainte de délai → NP-complet → P_D_E

  • Multicast

    • Distance / coût / délai → arbres optimaux (MST, Steiner, heuristiques polynomiales dans les cas simples) → P_E
    • Avec contrainte de délai → NP-complet → P_D_E

  • Broadcast

    • Distance / délai → arbre couvrant minimum (MST, BFS) → P_E
    • Coût de location → MST → P_E
    • Avec contrainte de délai → NP-complet (ex : Delay-Constrained MST, BDB heuristique) → P_D_E

⚠️ Phrase clé à écrire si le prof demande une justification

“L’ajout d’une contrainte de délai rend le problème NP-complet, donc il n’existe pas d’algorithme polynomial pour trouver la solution optimale.”

Si tu veux, je peux aussi te donner la version ultra-courte à apprendre par cœur ou te faire un contrôle blanc avec ce tableau.

Frage

ET EXE 1

Antwort

Parfait 👍
On fait EXERCICE 1 pas à pas, exactement comme au contrôle.

📌 Données de l’exercice (Exercice 1 – Chapitre 1)

Graphe (poids = délai) :

  • A–B = 3
  • B–C = 3
  • C–D = 1
  • D–E = 1
  • E–G = 1
  • G–F = 1
  • F–A = 1
  • A–H = 1
  • H–I = 5
  • I–E = 1

Source : A

🔹 a) Multicast

Source : A
Destinations : B, C, D, H
Objectif : minimiser le délai

👉 On cherche les plus courts chemins depuis A vers chaque destination, puis on prend l’union des chemins.

Plus courts chemins depuis A

  • Vers B :
    A → B = 3

  • Vers C :
    A → B → C = 3 + 3 = 6

  • Vers D :
    A → B → C → D = 3 + 3 + 1 = 7

  • Vers H :
    A → H = 1

🌳 Arbre multicast optimal (délai minimal)

Arêtes de l’arbre :

  • A–B
  • B–C
  • C–D
  • A–H

📌 C’est un arbre de plus courts chemins (SPT).

✅ Réponse (a)

L’arbre multicast optimal est :
A–B–C–D et A–H

🔹 b) Broadcast

Source : A
Destinations : tous les autres nœuds
Objectif : minimiser le délai

👉 En broadcast avec optimisation du délai → on construit l’arbre des plus courts chemins depuis A (SPT).

Plus courts chemins depuis A

  • F : A → F = 1
  • G : A → F → G = 2
  • E : A → F → G → E = 3
  • D : A → F → G → E → D = 4
  • C : A → F → G → E → D → C = 5
  • B : A → B = 3
  • H : A → H = 1
  • I : A → H → I = 6

🌳 Arbre de broadcast optimal (délai)

Arêtes retenues :

  • A–F
  • F–G
  • G–E
  • E–D
  • D–C
  • A–B
  • A–H
  • H–I

📌 Tous les nœuds sont atteints avec délai minimal depuis A.

✅ Réponse (b)

L’arbre optimal de broadcast est l’arbre des plus courts chemins depuis A : A–F–G–E–D–C, A–B, A–H–I

🧠 Astuce contrôle (très importante)

  • Multicast + délai → union des plus courts chemins vers les destinations
  • Broadcast + délai → arbre des plus courts chemins (SPT)
  • Broadcast + coût → MST

Si tu veux, je peux te faire le dessin exact de l’arbre comme sur copie, ou te donner la version ultra-courte à réciter 📝

Frage

Introduction.pdf

FAITE MOI QSM

Gedanke

All the files uploaded by the user have been fully loaded. Searching won't provide additional information.

Thought for a couple of seconds

Antwort

Voilà un QSM (QCM) prêt pour contrôle, basé sur Chapitre 1 : Optimisation du routage (exos + contrainte de délai) et un peu sur l’intro “Research Methodology” si ton prof mélange.
Je mets les réponses à la fin (comme ça tu peux t’entraîner).

QSM – Chapitre 1 (20 questions)

1) Unicast : optimiser la distance revient à chercher

A. Un arbre couvrant minimum
B. Un plus court chemin
C. Un arbre de Steiner
D. Un graphe complet

2) Unicast : l’algorithme classique pour plus court chemin (poids positifs) est

A. Prim
B. Kruskal
C. Dijkstra
D. Bellman-Ford uniquement

3) Broadcast : optimiser le coût total (un seul poids) correspond à

A. MST (Minimum Spanning Tree)
B. Plus court chemin
C. Arbre de Steiner avec délai
D. Max-flow

4) Multicast : connecter un groupe de destinations au moindre coût (cas général) est lié à

A. MST
B. Arbre de Steiner
C. BFS
D. Clique maximale

5) Quand on ajoute une contrainte de délai, trouver le chemin/arbre optimal devient

A. Toujours polynomial
B. NP-complet
C. Linéaire
D. Impossible même avec heuristiques

6) “Deux poids par arête” signifie typiquement

A. Deux sources
B. Coût + délai
C. Degré + distance
D. Puissance + ID

7) Dans le chapitre 1, on dit qu’on ne connaît pas d’algorithme polynomial pour l’optimal avec contrainte de délai parce que le problème est

A. Non orienté
B. NP-complet
C. Trop grand en mémoire
D. Non connexe

8) L’heuristique BDB (Bounded Delay Broadcasting) concerne

A. Unicast
B. Multicast
C. Broadcast (MST avec contrainte de délai)
D. Routage IP

9) Dans BDB, l’idée est : d’abord construire

A. Un arbre couvrant qui respecte le délai, puis réduire le coût sans casser le délai
B. Un MST puis ajouter un délai
C. Un plus court chemin puis supprimer des nœuds
D. Un graphe complet

10) Exercice 1 du poly : le poids sur les arêtes représente

A. Le coût de location
B. Le délai
C. La bande passante
D. Le nombre de sauts

11) Multicast (optimiser délai) : l’arbre attendu en général est

A. Union des plus courts chemins vers les destinations
B. Un MST global
C. Un arbre aléatoire
D. Un arbre complet

12) Broadcast (optimiser délai) : l’arbre attendu en général est

A. MST
B. Arbre des plus courts chemins depuis la source (SPT)
C. Arbre de Steiner
D. Cycle hamiltonien

13) Dans l’exemple “contrainte de délai = 14”, le chemin réponse du poly est

A. A–B–C–D–E
B. A–H–I–E
C. A–B–F–G–E
D. A–F–G–E

14) “P_E” dans le tableau signifie

A. Algorithme exponentiel existe
B. Algorithme polynomial existe pour l’optimal
C. On ne peut pas résoudre
D. C’est un graphe complet

15) “P_D_E” signifie

A. Algorithme polynomial n’existe pas (pour l’optimal)
B. Distance égale au délai
C. Problème linéaire
D. Route unique

16) (Tableau Exercice 2) Unicast avec contrainte de délai (optimiser coût ou distance) est classé

A. P_E
B. P_D_E
C. Toujours P_E si graphe petit
D. Toujours P_E si non orienté

17) (Tableau Exercice 2) Broadcast sans contrainte de délai (optimiser coût) est classé

A. P_D_E
B. P_E
C. NP-dur
D. Non défini

18) Dans l’heuristique de Kompella (Steiner avec contrainte de délai), l’étape 1 consiste à

A. Construire le MST sur le graphe original directement
B. Construire un graphe complet sur le groupe multicast avec coût = meilleur chemin contraint
C. Supprimer les arêtes chères
D. Faire un BFS

19) Dans Kompella, l’étape 2 consiste à

A. Trouver un MST (avec contrainte de délai) dans le graphe complet
B. Trouver un plus court chemin simple
C. Trouver un matching parfait
D. Trier les sommets

20) Dans Kompella, l’étape 3 consiste à

A. Remplacer chaque arête du MST du graphe complet par son chemin correspondant dans le graphe original
B. Inverser les arêtes
C. Ajouter un délai constant
D. Supprimer les destinations

✅ Corrigé (réponses)

  1. B
  2. C
  3. A
  4. B
  5. B (Cours5.pdf)
  6. B (Cours5.pdf)
  7. B (Cours5.pdf)
  8. C (Cours5.pdf)
  9. A (Cours5.pdf)
  10. B (Cours5.pdf)
  11. A (Cours5.pdf)
  12. B (Cours5.pdf)
  13. C (Cours5.pdf)
  14. B (Cours5.pdf)
  15. A (Cours5.pdf)
  16. B (Cours5.pdf)
  17. B (Cours5.pdf)
  18. B (Cours5.pdf)
  19. A (Cours5.pdf)
  20. A (Cours5.pdf)

Si tu veux, je te fais aussi un QSM “Exercice 1” (avec mini-calculs sur le graphe) ou un QSM “Vrai/Faux” (le prof aime ça souvent).

Diesen Q&A teilen