图中的桥
小于 1 分钟
图中的桥
在图论中，桥（bridge）、陆地峡（isthmus）、割边（cut-edge）或切割弧（cut arc）是指一条边，删除该边后会增加图的连通分量的数量。换句话说，如果一条边不包含在任何环中，则它是一条桥。如果图中不包含任何桥，则称该图为无桥图或无陆地峡图。
一个包含16个顶点和6条桥的图（用红色标出）
一个无桥图的无向连通图
关注公众号
和小伙伴们一起学习
加入技术交流群
扫描二维码 备注加群
在图论中，桥（bridge）、陆地峡（isthmus）、割边（cut-edge）或切割弧（cut arc）是指一条边，删除该边后会增加图的连通分量的数量。换句话说，如果一条边不包含在任何环中，则它是一条桥。如果图中不包含任何桥，则称该图为无桥图或无陆地峡图。
一个包含16个顶点和6条桥的图（用红色标出）
一个无桥图的无向连通图
和小伙伴们一起学习
扫描二维码 备注加群