News for hackers. Stuff that matters.
Re:Don't bring a tree to a mesh fight by GeneralMayhem on Thursday November 25, 2021 @12:46AM (#29338557)
I'm not saying that all hypergraphs - or all graphs - literally are bipartite graphs, I'm saying that you can construct a bipartite graph that represents the same structure as the hypergraph.

Given the hypergraph:

  A -> (B, C)
you can convert it to a bipartite graph by introducing an extra vertex of the second type to represent the hyper-edge:

  A -> e
  e -> B
  e -> C
You can do the same thing starting from a "regular" graph, although it's kind of silly for most purposes; for the basic cycle, you'd have:

  A -> e1
  e1 -> B
  B -> e2
  e2 -> C
  C -> e3
  e3 -> A
I'd say that's a much more valid representation of the graph than the spanning tree, which is lossy (since you can't tell from [A, B, C] whether or not there's an edge C->A).

There are no comments on this comment yet.