Hacker News new | past | comments | ask | show | jobs | submit login

You have a vertex set {A, B, C} and an edge set {A->B,B->C,C->A}. I'll label the edges D,E,F for convenience.

We define an incidence structure between the vertices and edges, by making red vertices to represent original vertices, and blue vertices to represent original edges. A directed edge A->B is represented by the path A->D->B in our incidence structure. In total, our incidence structure has six nodes {A,B,C,D,E,F} and six edges:

  A->D
  B->E
  C->F
  D->B
  E->C
  F->A
Said differently, we have subdivided every edge of the original graph into two edges in the incidence structure. That doubles the lengths of all cycles, so we don't see any odd cycles; also we have an explicit bipartition into red and blue.

All that said... directed hypergraphs are kinda wild.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: