进口饲料吧 关注:64贴子:487
  • 1回复贴,共1
求助

一笔画定理

只看楼主收藏回复



IP属地:山东1楼2023-03-31 08:16回复
    一笔画定理,任何有限的连通图都可以使用至多n条线段画出,其中n为该图中顶点的数目。由于该图是连通图,定义上存在一条从任意一个顶点到其他任一顶点的路径,因此可以通过n条线段将这些顶点全部连通,既画出了整个图。一笔画定理的推广,也可以应用到由多个连通图构成的联通图上,即在顶点数+边数不大于n的情况下,仍可以使用n条线段将该联通图全部画出。


    IP属地:河南2楼2023-03-31 11:14
    回复