4
$\begingroup$

Graphs are usually defined as a set of vertices $V$ together with a set of edges $E$ consisting of elements $V \times V$. I'm interested in a slight generalization of this, where instead one has two sets $V$, $W$ and the edges are taken from $V \times W$. The adjacency matrix of such an object would be rectangular, as opposed to the adjacency matrix of a regular old graph, which is square. Is there a name for this?

I'm interested in this because I'm writing a data structure to represent a graph in terms of its partitioning into sub-graphs for the purposes of parallel computation. For example, given a graph $G$ on a vertex set $V$, we can partition $V$ into disjoint subsets $V_1$ and $V_2$; $G$ is then naturally divided into two subgraphs $G_1$ and $G_2$ describing connections among $V_1$ and $V_2$ respectively, and a "rectangular graph" $H$ describing connections between $V_1$ and $V_2$. I'd like to give the class a name that makes sense.

$\endgroup$
5
$\begingroup$

Such a graph is known as a bipartite graph. There is a whole theory about bipartite graphs, including a number of algorithms that are specialized for bipartite graphs.

$\endgroup$
  • $\begingroup$ That's the word I'm looking for, thanks! $\endgroup$ – korrok Sep 12 '15 at 1:25

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.