2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I hope the two answers already given are sufficient to clarify the matter for you; if so, you should accept one of them. If they are not sufficient, then it might be useful to indicate in what way the two definitions (of "bipartite graph" and of "directed acyclic graph") look very similar to you. Then an answer might concentrate on clarifying that point. As it stands, the question is rather like "explain the difference between a goldfish and a rhinoceros." There are so many differences and so few similarities that it's hard to know how to answer. $\endgroup$ – Andreas Blass Aug 22 '14 at 2:07
1
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ What should we do with the titie? ... "bipartitie" $\endgroup$ – MacGyver Aug 21 '14 at 20:09
  • $\begingroup$ Fixed, probably a result of speaking Dutch natively. Thanks $\endgroup$ – Willem Van Onsem Aug 21 '14 at 20:47
  • $\begingroup$ I'm still trying to wrap my head around these. :-) I'm not a mathematician. $\endgroup$ – MacGyver Aug 21 '14 at 22:22
  • $\begingroup$ Updated with an image... $\endgroup$ – Willem Van Onsem Aug 21 '14 at 22:27
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.