哪种图的表达方法不能表示空图？

Which graph representation cannot represent an empty graph?

Question

哪种图的表达方法不能表示空图？

Which graph representation cannot represent an empty graph?

BlackTom AI · Accepted Answer

An edgeless graph (有顶点但无边的图) has one or more vertices but no edges. This is the key concept: some representations must explicitly record vertices, others only record edges.

Knowledge points and concepts
- Adjacency matrix: an n×n matrix; for n vertices it stores all vertex existence and edge info (all zeros if no edges).
- Adjacency list: for each vertex it stores a list of neighbors; vertices are explicit (each vertex maps to an empty list if no incident edges).
- Edge list: stores only pairs (u,v) for existing edges; it does not, by itself, list isolated vertices.

Step-by-step reasoning
1. Consider a simple example: vertices V = {1,2,3} and no edges E = ∅ (an edgeless graph).
2. Adjacency matrix: form a 3×3 matrix. Since there are no edges, every entry is 0. The matrix is
   [0 0 0
    0 0 0
    0 0 0]
   This unambiguously represents three vertices with no edges.
3. Adjacency list: form a mapping for each vertex: 1: [], 2: [], 3: []. This explicitly records three vertices and that none have neighbors.
4. Edge list: list all edges; since E = ∅, the edge list is simply []. An empty edge list contains no information about how many vertices exist — it could represent a graph with zero vertices or a graph with many isolated vertices. Standard edge-list format thus cannot represent the existence of isolated vertices without an auxiliary vertex list.

Why the correct answer is correct
- The edge list representation, by definition, only enumerates edges. For edgeless graphs it becomes empty and loses vertex-count information; therefore it cannot reliably represent an empty (edgeless-but-with-vertices) graph on its own.

Why the other options are incorrect
- Adjacency matrix explicitly encodes the number of vertices and edge presence (all zeros for edgeless), so it can represent the graph.
- Adjacency list explicitly lists each vertex with an empty neighbor list, so it can represent the graph.
- “None of these” is wrong because at least one representation (edge list) fails in this scenario.

Conclusion
Edge list (边列表) cannot represent an edgeless graph without additional vertex information, so the correct answer is: 边列表 Edge list.

哪种图的表达方法不能表示空图？ Which graph representation cannot represent an empty graph?单项选择题

类似问题

Which graph representation is more space-efficient for sparse graphs?

Tick all statements about graph representations that are correct.

Which of the following trees corresponds to a potential parse of the ambiguous sentence below, with correct syntactic categories? Some diagnostics are provided.

Which of the following sentences contain two non-finite verbs? Select all that apply.

Analyze the following sentence: The sentence contains [ Select ] 8 6 5 7 3 4 functional words, [ Select ] 2 3 1 4 5 count nouns, [ Select ] 4 5 2 1 3 mass nouns, and [ Select ] 1 5 2 3 4 adjectives.

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单