In a bidirected graph an edge has a direction at each end, so bidirectedgraphs generalize directed graphs. We generalize the definitions of transitiveclosure and transitive reduction from directed graphs to bidirected graphs byintroducing new notions of b-path and b-circuit that generalize directed pathsand cycles. We show how transitive reduction is related to transitive closureand to the matroids of the signed graph corresponding to the bidirected graph.
展开▼
