Quotient of a graph?

Question

I want to understand quotient of a graph (also called quotient graph), my teacher says that the terms quotient of a graph and a modulo of a graph should be synonyms (even though modulo of a graph returns something unexpected). I found this definition about the quotient graph

"Let $G = (V, E)$ be a graph. Let ∼ be an equivalence relation on $V$. The quotient graph of $G$ with respect to ∼ is a graph whose vertex set is the quotient set $V/∼$ and two equivalence classes $[u]$, $[v]$ form an edge iff $uv$ forms an edge in $G$."

What is the quotient of graph?

1. What is the quotient set $V/\sim$?

   1.1. In comparison, the quotient set on integers such as $\mathbb Z\ /\text{ division}$ consists of the quotient classes about the remainders. What are equivalent to "remainders" with graphs?

   1.2. What are the equivalence classes of a graph?

2. How is the quotient defined for a digraph?

Answer 1

I'll try to illuminate the definition you quoted with an example. Consider this graph of the subway map of Vienna:

By User:My Friend - Own Work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=7684906enter image description here

The vertices of this graph are the stations.

Define an equivalence relation on the set of vertices by

$v_1 \sim v_2 \mbox{ iff } v_1 \mbox{ is on the same subway line (e.g. U1, U2,...) as } v_2$.

Here, we need to modify the graph slightly and treat stations where you can change between lines (for example Westbahnhof) as two different, but connected vertices, i.e. Westbahnhof-U3 and Westbahnhof-U6 (you can think of these as different subway platforms instead of stations).

Then there are exactly five equivalence classes (as many as there are subway lines). These equivalence classes are sets of stations, e.g.

$$[\mbox{Heiligenstadt}]= \{\mbox{Heiligenstadt, Spittelau-U4, Friedensbrücke,}\dots\}.$$

Every stop on a given line is a member of the equivalence class associated with this line.

The definition of the edges on the quotient (that $[u][v]$ if $uv$) ensures the following: For two given equivalence classes of edges (i.e. subway lines), if there is a station which where you can switch between these lines (e.g. Westbahnhof-U3 and Westbahnhof-U6), then these equivalence classes are connected.

The resulting graph describes the connectedness of the subway lines, not the stops.

This results in a graph where U1 has an edge with U2, U3 and U4; U2 has an edge with U2, U3 and U4; U3 has an edge with U1, U2, U4, U6; U4 has an edge with U1, U2, U3 and U6; U6 has edge with U3 and U4. It should look like this, except the $5$ represents U6.

By Hafenbar from german Wikipedia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=15737112

Note that equivalence classes don't need to be connected, which is the case here.

For directed graphs, I cannot give more information, but my guess is that the definition of the (directed) edges carries over from the undirected case.

Answer 2

We refer to the enumerate list below on What is the quotient of the graph?

1. What is the quotient set $V/\sim$?

   1.1. In comparison, the quotient set on integers such as $\mathbb Z\ /\text{ division}$ consists of the quotient classes about the remainders. What are equivalent to "remainders" with graphs?

   1.2. What are the equivalence classes of a graph?

2. How is the quotient defined for a digraph?

---

(1.) What is the quotient set $V/\sim$?

The quotient set is the set of equivalence classes, in this case $$V/\sim\;=\{[v]:v\in V\}=\{\{x\in V:v\sim x\}:v\in V\}.$$ Note that (in general) the terms "quotient set of $X$" and "modulo of $X$" are equivalent (by definition) when referring to some equivalence relation $\sim$. For this reason, I would assume that the modulo of a graph is the graph with vertex set "$V$ modulo $\sim$" and edge set as described in your definition (in the same way that the quotient of a graph is the graph with vertex set "the quotient set of $V$ by $\sim$").

The quotient set $X/R$ is just a partition of $X$ which is "decided" by $R$. We might also do this the other way around, i.e. start with a partition $X=\bigcup X_i$, with $X_i\cap X_j=\emptyset$ whenever $i\neq j$, and let $xR y$ iff $\{x,y\}\subseteq X_i$ for some $i$. Then $X/R=\{X_i\}$. So in the same way, we might just view $V/\sim$ as some given partition of the vertex set $V$.

(1.1., 1.2.) The "remainders" are just the equivalence classes. I.e. in a quotient graph, the elements $[v]=\{x\in V:v\sim x\}$ of the quotient set $V/\sim$. Note that these are just sets of vertices which are given by the quotient on the set $V$ (no graph theory here) -- this definition will not differ from the standard equivalence classes of any old equivalence relation on some set.

For example, if $nRm$ iff $5|(n-m)$ (as in the answer to the linked question), the quotient set $\Bbb{Z}/R$ is $\{[0],[1],[2],[3],[4]\}$. In the division example, the classes are the sets of integers that have the same remainder when divided by $5$, and in the graph example, the classes are the sets of vertices defined by the equivalence relation $\sim$ (which we know nothing about).

(2.) How is the quotient defined for a digraph?

The definition is the same for a digraph, but it is written more nicely on the Wikipedia article on Quotient graph. To quote:

[I]f $G$ has edge set $E$ and vertex set $V$ and $R$ is the equivalence relation induced by the partition, then the quotient graph has vertex set $V/R$ and edge set $$\{([u]_R, [v]_R) : (u, v) \in E(G)\}.$$

(Recall, $(x,y)$ is understood to be an edge from $x$ to $y$ in a digraph.) So an edge in the quotient of $G$ exists from $[u]_R$ to $[v]_R$ iff there is an edge in $G$ from any vertex $u\in [u]_R$ to any vertex $v\in [v]_R$. An example of this is seen in this question. Here, the equivalence relation is given by $v\sim u$ iff there is a path from $v$ to $u$ and a path from $u$ to $v$. Hence (as given in the answer), the three classes are $[a]=\{a,b\}$, $[c]=\{c\}$, and $[d]=\{d,e,f,g,h\}$. I sketched the quotient graph below (excuse the Paint skills).

Regarding the reference request, I have never seen the definition in any graph theory textbook that I have read. Wikipedia's source seems to be High Quality Graph Partitioning (Peter Sanders, Christian Schulz) (pdf), which does have a definition that matches the one you reference, and the one I was familiar with. I have not found any source that uses "modulo" of a graph (in this context) but, as I mentioned before, this is likely due to the interchangeability of the terms when describing (general) equivalence relations.

Answer 3

I highlight the comment about a more general definition for quotient graph and bold the weakness in the original definition

The definition in your post is bad because it depends on the choice of representatives $u$ and $v$, so it isn't well defined in general. It should be worded: the edges in $V/∼$ are $$\{\{[u],[v]\}|\{u,v\}∈E\}.$$

that is the same, except notational differences, to the definition by Wikipedia Quotient Graph section provided by Szmagpie.