图论基础：关键概念与无向/有向图的性质详解

本资源主要涵盖了图论中的基础知识，包括图的基本概念、性质以及在不同类型的图（如无向图、有向图、连通图、完全图等）中的相关定理和特点。章节内容涉及选择题，考察了对图的路径定义、顶点与边的数量关系、连通性、有向图的边数、连通分量、图的度数、表达式解析、遍历方法、图的存储结构以及邻接矩阵的对称性分析。 1. **路径定义**：图中的路径是由顶点和它们之间的边按照特定顺序组成的序列，选项A正确地定义了路径为由顶点和相邻顶点序偶构成的边序列。 2. **顶点与边的数量**：无向图中，顶点个数为n的最大边数为n(n-1)/2，因为每增加一个顶点，都可以与之前的所有顶点形成一条边，但不包括重复的自环，所以B选项正确。 3. **连通图的边数**：连通无向图的边数至少为顶点数减一，即n-1，因为至少需要这样的一组边来确保所有顶点都相互连接，A选项正确。 4. **有向图的边数**：要使有向图连通，至少需要n-1条边，因为任意n个顶点可以形成一个有向树结构，这种情况下图是连通的，C选项正确。 5. **完全有向图边数**：n个顶点的完全有向图中，每个顶点都有一条指向其他每个顶点的边，总边数为n*(n-1)，D选项错误，B选项正确。 6. **连通分量**：一个图的连通分量最少有1个，即至少有一个连通的部分；最多有n个连通分量，当每个顶点形成一个单独的连通分量时，D选项正确。 7. **图的度数和边数关系**：无向图中所有顶点的度数之和是边数的两倍，而在有向图中，入度之和等于出度之和，均为所有顶点边数的总和，即1倍，B选项正确。 8. **表达式解析**：对于有向无环图(DAG)表示的表达式(A+B)*((A+B)/A)，至少需要5个顶点，因为至少需要一个A节点、一个B节点，以及两个分别代表加法和除法操作的顶点，A选项正确。 9. **遍历顺序**：DFS遍历无环有向图会得到拓扑有序的结果，B选项正确，因为DFS遵循先进后出的顺序。 10. **图的存储结构**：对于稀疏图，邻接表（包括无向图和有向图）是最适合的结构，因为它们可以高效地表示没有太多边的图；邻接矩阵适用于稠密图，而逆邻接表和邻接多重表常用于处理有向图，C和E选项可能指代邻接表，具体取决于上下文。 11. **邻接矩阵对称性**：邻接矩阵是对称的图是无向图，B选项正确，因为在无向图中，从一个顶点到另一个顶点的边与从另一个顶点到这个顶点的边是相同的。 12. **图的特征分析**：题目中给出了邻接矩阵的特征，但缺失了具体的数值，但从矩阵的结构可以判断出顶点数（①）、有向图的弧数（②，通常表示为双向边的数量）和无向图的边数（③）。 以上知识点覆盖了图论基础中的关键部分，有助于理解和解决与图相关的问题。