2012年电子科大图论期末考：填空+选择题详解

本资源是一份2012年电子科技大学的图论及其应用期末考试试卷，主要考察了图论的基本概念和性质。以下是部分内容的详细解析： 1. **n阶k正则图的边数** - 在图论中，一个n阶k正则图意味着每个顶点都有k条边相连。对于这样的图，边数m可以通过公式计算：m = kn。因为每个顶点贡献k条边，n个顶点总边数就是kn。 2. **不同构简单图的数量** - 当有3个顶点时，考虑不同的连线方式，即顶点间的连接组合。对于3个顶点的简单图，没有自环和重复边，所以可能的连通结构有完全图（3条边）、无边的树（0条边）以及1条边的星型图，总共3种不同的图。 3. **简单图的生成子图个数** - 边数为m的简单图的所有生成子图包括从原图中选取边的不同组合。由于每个边都是独立的，生成子图的个数是2的m次方，即2^m，这是因为每一个边都可以存在或不存在于子图中。 4. **积图的边数** - 如果有两个图G1和G2，它们的积图G1×G2的边数可以通过将两个图的边数相乘得到，即m(G1×G2) = m(G1) × m(G2)。 5. **最短路径问题** - 求解两点间最短距离的问题，在图G1中，点a到点b的最短长度取决于它们之间的实际路径，需要根据具体图的结构来计算。 6. **邻接矩阵与边数** - 根据邻接矩阵A计算图G的边数，注意到矩阵中1表示相邻，非1表示不相邻。图G的边数等于矩阵中1的总数，即所有非零元素的和。 7. **简单图的边数限制** - 对于不含完全子图K3的n阶简单图，K3有3个顶点和3条边，所以这样的图不能有过多的边，边数m≤n(n-1)/2，因为这个极限值是完全图K_n的最大边数。 8. **K3生成树的棵树** - K3是最小的三角形，其生成树只有一棵，因为树是最少边数的连通图，而K3本身已是最小的连通图。 9. **图的连通性指标** - 点连通度k(G)指的是通过最少删除几个点使得图变为不连通；边连通度λ(G)表示最少删除几条边使图不再连通；最小度δ(G)是图中任意顶点的度数的最小值。这三者的关系是：k(G)≤λ(G)≤δ(G)。 10. **图的分类** - 提供的图示表格中，需要判断哪些图满足特定条件。例如，是否能一笔画（欧拉图），是否存在哈密尔顿回路（Hamiltonian图），是否为偶图（没有奇数长度的回路）或可平面图（可以嵌入到二维平面上）。 这份试卷覆盖了图论的基础概念，如正则图、生成子图、最短路径、邻接矩阵、简单图的边数限制、连通性和图的特殊性质等，并通过填空题和选择题的形式进行考核，适合用于检验学生对图论的理解程度。