Graphs and networks · Grafos y redes
| English | Español |
|---|---|
| graph/ɡræf/ | graficar |
| vertices/ˈvɜːtɪsiːz/ | vértices |
| edges/ˈedʒɪz/ | bordes |
| degree/dɪˈɡriː/ | grado |
| path/pæθ/ | ruta |
| cycle/ˈsaɪkl/ | ciclo |
| connected/kəˈnektɪd/ | conectado |
| tree/triː/ | árbol |
| weighted graph/ˈweɪtɪd ɡræf/ | grafo ponderado |
| shortest path/ˈʃɔːtɪst pæθ/ | camino más corto |
A connection model needs its assumptions
- A graph 图 has vertices 顶点 and · y 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 · ruta 路径 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.
In a simple undirected graph without loops, four edges meet a vertex. What is its degree? · En un grafo simple no dirigido sin bucles, cuatro aristas se encuentran en un vértice. ¿Cuál es su grado?
Its degree is 4, the number of incident edges under the stated graph convention. · Su grado es 4, el número de aristas incidentes bajo la convención de grafos declarada.
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.
A tree has 4 vertices. How many edges does it have? · Un árbol tiene 4 vértices. ¿Cuántas aristas tiene?
A finite tree with four vertices has n − 1 = 3 edges. This count depends on the graph actually being connected and acyclic. · Un árbol finito con cuatro vértices tiene n − 1 = 3 aristas. Este conteo depende de que el grafo sea realmente conexo y acíclico.
In a connected undirected network with strictly positive edge costs, why does a minimum-cost connected subgraph spanning all vertices contain no cycle? · En una red conectada no dirigida con costos de arista estrictamente positivos, ¿por qué un subgrafo conectado de costo mínimo que abarca todos los vértices no contiene ciclos?
Removing any cycle edge preserves connectivity and lowers total cost because its weight is strictly positive. Thus a cyclic subgraph cannot be minimum under these assumptions. · La eliminación de cualquier arista de ciclo preserva la conectividad y reduce el costo total porque su peso es estrictamente positivo. Por lo tanto, un subgrafo cíclico no puede ser mínimo bajo estas suposiciones.
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.
Match each situation to what its vertices and edges should be. · Empareja cada situación con lo que deberían ser sus vértices y aristas.
Deciding what the vertices represent is the modelling step, and it is where the marks are. · Decidir qué representan los vértices es el paso de modelado, y es ahí donde se obtienen los puntos.
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.
Two drawings that look different must be different graphs. · Dos dibujos que parecen diferentes deben ser grafos diferentes.
Different layouts can have the same labelled adjacency. Compare directions and weights as well when those are part of the specified graph. · Diferentes configuraciones pueden tener la misma adyacencia etiquetada. Compare también las direcciones y los pesos cuando estos forman parte del grafo especificado.
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.