underlying_undirected_graph (493B)
1 # Underlying undirected graph 2 3 Given a [directed_graph] G = (V, E), its *underlying undirected graph* is the 4 [undirected_graph] G' = (V, E') obtained by taking E' = {{u, v} \mid (u,v) \in 5 E}. 6 7 - May contain [multiedges] if some vertices are connected by an edge in both directions 8 - May contain [self_loops] if G did 9 - We may alternatively define G' as an [undirected_graph] without [multiedges] or [self_loops] by discarding [self_loops] and multiple edge occurrences 10 11 Up: [graph_operations]