论文标题
b-articulation Points和b-Bridges在强烈双连接的有向图中
b-articulation points and b-bridges in strongly biconnected directed graphs
论文作者
论文摘要
如果$ g $连接$ g $，并且$ g $的基础图是双连接的，则指示图$ g =（v，e）$被称为强烈双连接。这类定向图最初是由Wu和Grumbach引入的。令$ g =（v，e）$是一个强烈双连接的有向图。如果子图$ g \ setMinus \ left \ lbrace e \ right \ rbrace =（v，e \ setminus \ left \ laws \ lbrace e \ right \ rbrace $），e $中的边缘$ e \是b桥。如果$ g \ setminus \ left \ lbrace w \ right \ rbrace $不是强烈的双重连接，则V $中的顶点$ w \是一个b-提示点，其中$ g \ setminus \ setMinus \ left \ lbrace w \ lbrace w \ rbrace \ rbrace $ rbrace $是从$ g $中获得的$ g $。在本文中，我们研究了b-articulation Points和b-bridges。
A directed graph $G=(V,E)$ is called strongly biconnected if $G$ is strongly connected and the underlying graph of $G$ is biconnected. This class of directed graphs was first introduced by Wu and Grumbach. Let $G=(V,E)$ be a strongly biconnected directed graph. An edge $e\in E$ is a b-bridge if the subgraph $G\setminus \left\lbrace e\right\rbrace =(V,E\setminus \left\lbrace e\right\rbrace) $ is not strongly biconnected. A vertex $w\in V$ is a b-articulation point if $G\setminus \left\lbrace w\right\rbrace$ is not strongly biconnected, where $G\setminus \left\lbrace w\right\rbrace$ is the subgraph obtained from $G$ by removing $w$. In this paper we study b-articulation points and b-bridges.
