commit da2b33a1ffb7001e20710bedb8f399df5eede914
parent c72ecccaac43da03d47aa1fa7df62c62e53ee711
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 14 Jan 2025 15:57:48 +0100
commit with codex
Diffstat:
9 files changed, 46 insertions(+), 6 deletions(-)
diff --git a/connected_component b/connected_component
@@ -2,6 +2,8 @@
An [equivalence_class] of the [reachability] [equivalence_relation] in an [undirected_graph]
-See also: [strongly_connected_component]
+- [weakly_connected_component]
+
+See also: [strongly_connected_component], [graph_connected]
Up: [graph_basic_notions]
diff --git a/graph_directed b/graph_directed
@@ -1,9 +1,10 @@
# Graph directed
-[graph] where [edge]s are [ordered_pair]s
+A [graph] where [edges] are [ordered_pairs]
- [directed_acyclic_graph]
- [graph_period]
+- [underlying_undirected_graph]
Up: [graph]
diff --git a/graph_operations b/graph_operations
@@ -0,0 +1,8 @@
+# Graph operations
+
+- [graph_union]
+- [graph_product]
+- [edge_contraction]
+- [underlying_undirected_graph]
+
+Up: [graph]
diff --git a/multiedge b/multiedge
@@ -0,0 +1,7 @@
+# Multiedge
+
+An [edge] in a [multigraph], which has a [multiplicity] (= may exist multiple times)
+
+Up: [edge], [multigraph]
+
+Aliases: multiedges
diff --git a/multigraph b/multigraph
@@ -1,6 +1,6 @@
# Multigraph
-A [graph] where the same [edge] can exist multiple times.
+A [graph] where the same [edge] can exist multiple times, called a [multiedge]
Can also be seen as a [weighted_graph] where edges carry a nonzero integer weight
diff --git a/strongly_connected_graph b/strongly_connected_graph
@@ -1,7 +1,7 @@
# Strongly connected graph
-s
-
A [directed_graph] having one [strongly_connected_component]
-Up: [strongly_connected]
+Up: [directed_graph], [strongly_connected]
+
+See also: [graph_connected], [weakly_connected_graph]
diff --git a/underlying_undirected_graph b/underlying_undirected_graph
@@ -0,0 +1,8 @@
+# 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}.
+
+- May contain [multiedges] if some vertices are connected by an edge in both directions
+- May contain [self_loops] if G did
+
+Up: [graph_operations]
diff --git a/weakly_connected_component b/weakly_connected_component
@@ -0,0 +1,7 @@
+# Weakly connected component
+
+In [directed_graphs], a *weakly connected component* is a [connected_component] of the [underlying_undirected_graph]
+
+Up: [connected_component]
+
+See also: [strongly_connected_component]
diff --git a/weakly_connected_graph b/weakly_connected_graph
@@ -0,0 +1,7 @@
+# Weakly connected graph
+
+A [directed_graph] which is [weakly_connected], i.e., has only one [weakly_connected_component]
+
+Up: [directed_graph]
+
+See also: [strongly_connected_graph]
