一种任意无向图的R边连通扩充算法

本文提出了一个最小地扩充任意无向连通图为 R 边连通图的有效算法RMA。该算法采用了“先满足必要条件,再满足充要条件”的指导思想。对于一个任意无向连通图,首先将图中各点扩充到它所要求的最小度,然后检查它是否满足充要条件,如果不满足,则将该图分解,再根据最优程则,增加扩充边。将图合并,最后进行可行删除,解雇增广点,得到一个最小 R 边连通图。