commit b8f3d6416e4da4d1a6022e38d5b633bb3633f4aa
parent 42afe5cfaaf51d1e27f98ce8a6414871426af90a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 27 Oct 2025 17:06:12 +0100
commit with codex
Diffstat:
2 files changed, 9 insertions(+), 2 deletions(-)
diff --git a/cutwidth_directed b/cutwidth_directed
@@ -1,5 +1,9 @@
-# Cutwidth directed
+# Directed cutwidth
introduced in [chudnowski2012tournament]
+Not the same as the [cutwidth] of the [underlying_undirected_graph] of a [directed_graph]
+
Up: [cutwidth] on [directed_graphs]
+
+Aliases: directed cutwidth
diff --git a/underlying_undirected_graph b/underlying_undirected_graph
@@ -1,8 +1,11 @@
# Underlying undirected graph
-Given a [directed_graph] G = (V, E), construct an [undirected_graph] G' = (V, E') by taking E' = {{u, v} \mid (u,v) \in E}.
+Given a [directed_graph] G = (V, E), its *underlying undirected graph* is the
+[undirected_graph] G' = (V, E') obtained by taking E' = {{u, v} \mid (u,v) \in
+E}.
- May contain [multiedges] if some vertices are connected by an edge in both directions
- May contain [self_loops] if G did
+- We may alternatively define G' as an [undirected_graph] without [multiedges] or [self_loops] by discarding [self_loops] and multiple edge occurrences
Up: [graph_operations]
