Graphes et réseaux
Introduit| English | Sens |
|---|---|
| graph/ɡræf/ | graphe |
| vertices/ˈvɜːtɪsiːz/ | sommets |
| edges/ˈedʒɪz/ | arêtes |
| degree/dɪˈɡriː/ | degré |
| path/pæθ/ | chemin |
| cycle/ˈsaɪkl/ | cycle |
| connected/kəˈnektɪd/ | connecté |
| tree/triː/ | arbre |
| weighted graph/ˈweɪtɪd ɡræf/ | graphe pondéré |
| shortest path/ˈʃɔːtɪst pæθ/ | plus court chemin |
A connection model needs its assumptions
- A graph 图 has vertices 顶点 and edges 边. Decide what they represent and whether the connections are directed, weighted or undirected.
- The worksheet uses finite simple undirected graphs without loops or repeated edges. Drawing position does not change their connections, but an arrow or edge weight can change the mathematical model.

Count connections consistently
- Degree 度 counts incident edges in a simple undirected graph. The total degree is twice the number of edges, so it must be even.
- A path 路径 follows connections; a cycle 环 returns to its start without repeating other vertices. A graph is connected 连通 when each vertex can be reached from every other.
Dans un graphe simple non orienté sans boucles, quatre arêtes incident à un sommet. Quelle est sa degree (degré) ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Son degré est 4, le nombre d'arêtes incidentes selon la convention de graphe déclarée.
A tree needs two properties
- A tree 树 is connected and has no cycles. A finite tree with n vertices has n minus 1 edges.
- Having n minus 1 edges alone does not prove a tree: a triangle plus a separate two-vertex component has five vertices and four edges but is disconnected and cyclic.
Un arbre a 4 sommets. Combien d'arêtes a-t-il ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Un arbre fini à quatre sommets a n − 1 = 3 arêtes. Ce comptage dépend du fait que le graphe soit effectivement connecté et acyclique.
Dans un réseau connexe non orienté avec des coûts d'arête strictement positifs, pourquoi un sous-graphe de coût minimal connectant tous les sommets ne contient-il aucun cycle ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Retirer une arête de cycle préserve la connectivité et réduit le coût total car son poids est strictement positif. Ainsi, un sous-graphe cyclique ne peut être minimal sous ces hypothèses.
Positive-cost connecting roads. For a connected network with strictly positive road costs, removing a cycle edge leaves connectivity and lowers cost. A minimum-cost connecting subgraph is therefore a tree. To find a minimum spanning tree, choose edges that connect all vertices without a cycle; blindly choosing the cheapest n minus 1 edges can leave separate components.
A shortest route is not a spanning tree
- A weighted graph 带权图 attaches a specified value to each edge. A shortest path 最短路径 minimises route weight between the given endpoints.
- A minimum spanning tree instead connects every vertex at minimum total included weight. A shortest route can have more edges than a direct expensive route; sum the weights rather than count the edges.
Reliez chaque situation à ce que ses sommets et arêtes devraient représenter.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Décider ce que représentent les sommets est l'étape de modélisation, et c'est là que se trouvent les points.
A closed edge changes feasibility. Sheet 4.5 finds a route of weight 7, then closes an edge and checks a replacement of weight 9. Do not reuse the old total for a path that no longer exists.
Deux dessins différents doivent être considérés comme différents graphes.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Des mises en page différentes peuvent avoir la même adjacence étiquetée. Comparez également les directions et les poids lorsque ceux-ci font partie du graphe spécifié.
Compare all structure relevant to the question: vertex correspondence, adjacency, directions and weights where specified. Equal-looking pictures need not represent the same graph; different layouts can represent the same labelled connections.