2025.4.1 海亮讲题
耳分解
耳、开耳
一个子图的耳是指一个简单路径或简单环，开头和结尾都在子图上，而中间经过的点不在子图上。耳不能是一个点。
如果它不是简单环，那么同时称之为开耳。
耳分解
耳分解是指构造出 从一个环出发，每次加上一个耳，最后达到整个图 的操作序列。
定理
无向图耳分解存在的充要条件是此图边双联通。
有向图耳分解存在的充要条件是此图强连通。
使用tarjan算法可以做耳分解，但是我没听见。
应用
将边双联通的无向图标出边向转化为强连通的有向图。只需做一个耳分解就行了。
一个子图的耳是指一个简单路径或简单环，开头和结尾都在子图上，而中间经过的点不在子图上。耳不能是一个点。
如果它不是简单环，那么同时称之为开耳。
耳分解是指构造出 从一个环出发，每次加上一个耳，最后达到整个图 的操作序列。
无向图耳分解存在的充要条件是此图边双联通。
有向图耳分解存在的充要条件是此图强连通。
使用tarjan算法可以做耳分解，但是我没听见。
将边双联通的无向图标出边向转化为强连通的有向图。只需做一个耳分解就行了。