习 题 1.1 试证，任意有向图所有顶点出度之和等于其人度之和且等于边的条数。 1.2 试证，任意有向完全图所有顶点出度平方之和等于其人度平方之和。 1.3 试证，任意简单无向图的最大度小于顶点数。 1.4 在图同构的观点下，试画出拥有三个顶点的所有简单有向图。并说明它们是否具有对称性、反对称性和传递性等特征。 1.5 试确定图1－ 1 中两个有向图是否同构。 图 1－ 1 1． 6 试确定图1－ 2 中两个有向图是否同构。 图 1－ 2 1． 7 试证图1－ 3 中两个无向图是不同构的。 图 1－ 3 1． 8 试确定图1－ 4 中两个无向图是否同构。 图 1－ 4 1． 9 试证图1－ 5 中两个无向图是同构的。 图 1－ 5 1． 10 设 G 是拥有四个顶点的无向完全图。在图同构的观点下，试求： 1） G 的所有子图。 2） G 的所有生成子图。 1． 11 试求1.4 中各简单有向图的补图。 1． 12 试求图1－ 6 中各简单图的补图： 图 1－ 6 1． 13 简单无向图若同构于它的补图，则该图称自补图。 1）试给出四和五个顶点的自补图。 2）是否有三或六个顶点的自补图？ 1． 14 对图1－ 7 的有向图 1）试求从顶点 到 的三条不同的基本路径。 2）顶点 到 的距离是多少？ 3）此图是否有循环？ 4）试求此图的可传递闭包。 图 1－ 7 1． 15 设在无向图G 中，从顶点 到 有一条长度为偶数的基本路径，又有一条长度为奇数的基本路径。试证,G 中必有一条长度为奇数的基本循环。 1． 16 对图1－ 8 的有向图 图 1－ 8 1）试求各顶点的出度和入度。 2）试求所有基本循环。 3）删去哪条边能得到一个非循环图？ 1． 17 设 个城市由 条公路连结。试证，若 ， 则人们总能通过这些公路,在任意两个城市之间旅行。 1． 18 设有 等七人，其中 会讲英语； 会讲华语和英语； 会讲英语，意大利和俄语； 会讲华语和日语； 会讲德语和意大利语； 会讲法语，日语和俄语； 会讲法语和德语。试问：必要时借助于其他人的转译，这七个人中，是否任意两个人都能交谈？ 1． 19 试证，当且仅当无向连通图G 的一条边 不包含在G 的基本循环中时， 才是割边。 1． 20 试证，当且仅当无向连通图G 的一个顶点 ，存在两个不同顶点 和 ，使所有 到 的基本路径都通过 时， 才是割点。 1． 21 对 1.14和 1.16中的有向图，试确定它们是否为弱连通的，单向连通的或是强连通的。 1...
