离散数学习题解答习题六（第六章 图论）.doc

离散数学习题解答习题六 （第六章 图论）1从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。解 用V代表全国城市的集合，E代表各城市间的铁路线的集合，则所成之图G=（V，E）是全国铁路交通图。是一个无向图。V用代表中国象棋盘中的格子点集，E代表任两个相邻小方格的对角线的集合，则所成之图G=（V，E）是中国象棋中“马”所能走的路线图。是一个无向图。用V代表FORTRAN程序的块集合，E代表任两个程序块之间的调用关系，则所成之图G+（V，E）是FORTRAN程序的调用关系图。是一个有向图。2画出下左图的补图。 图解 左图的补图如右图所示。v1v2v3v4v5v6v6v13证明下面两图同构。图G图Gv5v4v3v2 证 存在双射函数j:VV及双射函数y : EEj (v1)=v1j (v1，v2)=(v1，v2)j (v2)