数据结构考研分类复习真题 第七章 图[27]

数据结构考研分类复习真题 第七章 图[27]  

　　四 应用题

　　 ．( )．如果G 是一个具有n个顶点的连通无向图 那么G 最多有多少条边？G 最少有多少条边？

　　( )．如果G 是一个具有n个顶点的强连通有向图 那么G 最多有多少条边？G 最少有多少条边？

　　( )．如果G 是一个具有n个顶点的弱连通有向图 那么G 最多有多少条边？G 最少有多少条边？【复旦大学 一( 分)】

　　 ．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？【山东大学 一   ( 分)】

　　 ．一个二部图的邻接矩阵A是一个什么类型的矩阵？【北京科技大学 一 ( 分)】

　　 ．证明 具有n个顶点和多于n 条边的无向连通图G一定不是树 【东南大学 四( 分)】

　　 ．证明对有向图的顶点适当的编号 可使其邻接矩阵为下三角形且主对角线为全 的充要条件是该图为无环图 【北京邮电大学 三 ( 分)】

　　 ．用邻接矩阵表示图时 矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？【西安电子科技大学 计应用 一 ( 分)】