0
$\begingroup$

I'm working on a task I dont really understand. It says

"Define the relation $R\subset \mathbb{ℕ} × \mathbb{ℕ}$ by: $R = \{(a,b) \in \mathbb{N} : a-2 \le b \le a+2\}$.

Draw the graph of the relation, restricted on the natural numbers between $0$ and $10$. Expected answer (motivated): A graph, with $11$ vertices, and an arrow pointing from $V_1$ and $V_2$ if $(V_1, V_2) \in R$."

So $R\subset \mathbb{ℕ} × \mathbb{ℕ}$. $\mathbb{N} \times\mathbb{N}$ is $\{(0,0),(0,1),(0,2),...\}$ and so on all the way to $10$, then $\{(1,0), (1,1), ...\}$ all the what to $10$ agan, and again and so on. U get the point. So I now what kind of numbers I am suppose to work with. When I get to the $R = \{(a,b) ∈ ℕ : a-2 ≤ b ≤ a+2\}$ part, it's kind of more confusing. $(a,b) \in\mathbb{N}$ is fair enough. "$a$" and "$b$" could be a number between $0-10$. The last part is okey too, just choose a number for $a$ and $b$ from set $R$. If true it is in the relation. But how should I draw a graph out of this? I don't kind of see the connection between.
Thanks for all answer! :D

$\endgroup$
  • 2
    $\begingroup$ The basic idea is that you write the numbers $0, 1, 2, ..., 10$ out on a piece of paper and then connect the two numbers $a$ and $b$ if $(a, b) \in R$. Each number is a vertex and $R$ represents the edge list. $\endgroup$ – Noble Mushtak Jun 9 '16 at 19:43
  • $\begingroup$ Are you familiar with the notion of a combinatorial graph? See en.wikipedia.org/wiki/Graph_(discrete_mathematics). $\endgroup$ – Jakob Hansen Jun 9 '16 at 19:44
4
$\begingroup$

Would the graph look something like this? : enter image description here

My drawing skills is not at a top level today, but I think this is how the graph should look like if I did understand u guys right. NOTE: The both way arrows are suppose to be two separated arrow, I just draw both way arrows to save some space. I dont know if it matters.

$\endgroup$
  • $\begingroup$ This is correct. Great job! $\endgroup$ – Noble Mushtak Jun 9 '16 at 20:09
  • $\begingroup$ Okey, nice! Thanks 4 the help! :D $\endgroup$ – Christian Iversen Jun 9 '16 at 20:10
1
$\begingroup$

They want you to create a graph where $0, 1, 2, .., 10$ are the verticies and the vertices are connected if and only if $(a, b) \in R$. The relation $R$ is basically an edge list for this graph. We know that: $$(a, b) \in R \iff a-2 \leq b \leq a+2$$

However, this inequality can be more succinctly written as $\lvert a-b \rvert \leq 2$. Thus, two vertices are connected if they have a difference less than or equal to $2$. If we examine each vertex individually, we find:

  • $0$ will be connected to $0, 1, 2$
  • $1$ will be connected to $0, 1, 2, 3$
  • $2$ will be connected to $0, 1, 2, 3, 4$
  • $3$ will be connected to $1, 2, 3, 4, 5$
  • $4$ will be connected to $2, 3, 4, 5, 6$
  • $5$ will be connected to $3, 4, 5, 6, 7$
  • $6$ will be connected to $4, 5, 6, 7, 8$
  • $7$ will be connected to $5, 6, 7, 8, 9$
  • $8$ will be connected to $6, 7, 8, 9, 10$
  • $9$ will be connected to $7, 8, 9, 10$
  • $10$ will be connected to $8, 9, 10$

Thus, by using this rule of connected the vertices of numbers $0, 1, 2, ..., 10$, we can represent $R$ using a graph.

$\endgroup$
  • $\begingroup$ Yeah, that's what I have done, but I have that all the vertices is also connected to them self, since it is true with this statement: a−2≤b≤a+2 $\endgroup$ – Christian Iversen Jun 9 '16 at 20:01
  • $\begingroup$ @ChristianIversen That is correct. All of the vertices are connected to themselves. $\endgroup$ – Noble Mushtak Jun 9 '16 at 20:05
  • $\begingroup$ So the picture I added as an answer is how the graph should look like, right ? $\endgroup$ – Christian Iversen Jun 9 '16 at 20:06
1
$\begingroup$

Start with $0.$ (0,0)(0,1),(0,2) are in R.

Make nodes for $0, 1$ and $2$ and draw your arrows from $0 \to 1$ and $0 \to 2$ and a little loop from 0 to itself.

What is $1$ related to? (1,0),(1,1,),(1,2),(1,3).

Make a node for $3$ that is somewhere convenient. Double end the existing arrow $0\iff 1$, make your arrows for $1\to2$ and $1\to3$, and the loop from 1 to 1.

etc.

$\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.