What is meant by "restriction" in subgraph definition

1.1k Views Asked by At

In the book "Graph Theory with Application" by Bondy and Murthy it is defined that

A graph $H$ is a subgraph of G if $V(H) \subset V(G)$, $E(H) \subset E(G)$ and $\psi_H$ is the restriction of $\psi_G$ to $E(H)$.

I am a beginner and couldn't understand "$\psi_H$ is the restriction of $\psi_G$ to $E(H)$.".

For a Computer Science student and beginner how would you explain that?

1

There are 1 best solutions below

0
On BEST ANSWER

TL;DR

We say that function $g$ is a restriction of $f : X \to Y$ to set $X' \subseteq X$, written $$g = f\,\Big|_{X'}$$ when the domain of $g$ is $X'$ and $g(x) = f(x)$ for all $x \in X'$.

Usual definition of a graph:

Usually a graph is defined as a pair $G = \langle V, E \rangle$ where $E \subseteq V \times V$ is a relation on $V$ that describes edges. For example, a triangle-like directed graph would be

$$\newcommand{tuple}[1]{\left\langle #1 \right\rangle} G_1 = \Big\langle \{1,2,3\}, \big\{\tuple{1,2},\tuple{2,3},\tuple{3,1}\big\} \Big\rangle. \hspace{50pt} \begin{array}{c} 1 &\to & 2 \\ \uparrow &\swarrow\\ 3 \end{array} $$

In such a setting, a graph $H$ is defined to be a subgraph of $G$ when $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$. For example, $H_1$ is a subgraph of $G_1$

$$H_1 = \Big\langle \{1,2,3\}, \big\{\tuple{2,3},\tuple{3,1}\big\} \Big\rangle. \hspace{50pt} \begin{array}{c} 1 & & 2 \\ \uparrow &\swarrow\\ 3 \end{array} $$

Definition with incidence function:

In "Graph Theory with Application" of Bondy and Murthy the graph is defined as a triple $G = \tuple{V,E,\psi}$ where $E$ is just any set (you can think of it as index set), and the edge-relation is described by $\psi$. The above graph would look like

\begin{align} G_1 &= \Big\langle\{1,2,3\}, \{100,200,300\},\psi_1\Big\rangle, \\ \psi_1(e) &= \begin{cases} \tuple{1,2} & \text{ if } e = 100, \\ \tuple{2,3} & \text{ if } e = 200, \\ \tuple{3,1} & \text{ if } e = 300. \\ \end{cases} \end{align}

Now, to define a subgraph, we need take care of $\psi$ as well, and the authors restrict the relevant function to the new domain. In other words, the domain of $\psi_1$ was $\{100,200,300\}$. Now, in the subgraph we don't have edge $100$, and the domain of $\psi_2$ is $\{200,300\}$. Mathematical notation for this is $$\psi_2 = \psi_1\Big|_{\{200,300\}}$$ that is, $\psi_2$ is defined to take the same values as $\psi_1$, but its domain is smaller, i.e. is a subset of domain of $\psi_1$. To give an explicit example:

\begin{align} H_1 &= \Big\langle\{1,2,3\}, \{200,300\},\psi_1'\Big\rangle, \\ \psi_1'(e) &= \begin{cases} \tuple{2,3} & \text{ if } e = 200, \\ \tuple{3,1} & \text{ if } e = 300. \\ \end{cases} \end{align}

Some comments:

The two definitions are equivalent, i.e. you can get the usual set $E_\text{pair}$ with $\psi(E_\text{triple})$, and you can get the incidence function by setting $E_\text{triple} = E_\text{pair}$ and $\psi(e) = e$ (there is nothing on what $E_\text{triple}$ should be, so we can make it $E_\text{pair}$ for simplicity, why not).

However, there is a small difference; with triple-definition you can change the set of edges without changing the structure of the graph, i.e.

$$ \Big\langle\{1,2\},\{100\}, \psi(100) = \tuple{1,2}\Big\rangle $$ and $$ \Big\langle\{1,2\},\{\spadesuit\}, \psi(\spadesuit) = \tuple{1,2}\Big\rangle $$

are two different graphs even if their structure is the same. With the standard definition you need to change the set of vertices (or at least permute them). It might be useful, but I'm not sure it justifies the increase in complexity.

I hope this helps $\ddot\smile$