bipartite graph vs. directed acyclic graph

Question

I'm having a hard time understanding the fundamental differences between a directed acyclic graph and a bipartite graph. Can anyone see how they are different from a mathematics perspective (or data modeling perspective)? Or are they just used in different contexts?

Answer 1

The two definitions don't have that much in common.

---

In a bipartite graph, the vertices $V$ are subdivided into two sets $V_1$ and $V_2$, and only edges between $V_1$ and $V_2$ are allowed.

---

In a directed acyclic graph (DAG), the edges are directed, but if $v_1$ is (directed) connected to $v_2$, there is no directed path from $v_2$ to $v_1$.

---

If the bipartite graph is thus directed from $V_1$ to $V_2$, such graph is a DAG. On the other hand a similar tri-partite graph is a DAG as well.

Based on Tarjans topological ordering algorithm. One can always subdivide a directed acyclic graph into partitions. But the number of partitions is not limited to $2$.

To visualize (vizualize at http://graphviz-dev.appspot.com/), this is a bipartite digraph (and thus an (undirected) acyclic graph):

graph g{
  a - e;
  a - f;
  b;
  c - e;
  d - f;
}

This is a directed acyclic graph, but not a digraph.

digraph g{
  a -> e;
  a -> f;
  b;
  c -> e;
  d -> f;
  e -> f;
}

Answer 2

The two concepts are entirely different.

A directed acyclic graph is a graph $G$ so that for any two vertices $v_1, v_2 \in V(G)$ if there is a directed path from $v_1$ to $v_2$ in $G$, then there is no directed path from $v_2$ to $v_1$ in $G$.

A bipartite graph is a graph $G$ so that $V(G)$ can be partitioned into two sets $V_1$ and $V_2$ so that all edges of $G$ are between a vertex of $V_1$ and a vertex of $V_2$.

A directed acyclic graph need not be bipartite, and a directed bipartite graph need not be acyclic. For example, the graph on 3 vertices with directed edges $\{v_1 \rightarrow v_2, v_1 \rightarrow v_3, v_2 \rightarrow v_3\}$ is a directed acyclic graph, but is not bipartite. The graph on 4 vertices with directed edges $\{v_1 \rightarrow v_2, v_2 \rightarrow v_3, v_3 \rightarrow v_4, v_4 \rightarrow v_1\}$ is bipartite, but is not directed acyclic.