Link between Graph of function & Graph theory

573 Views Asked by At

Definition for graph of function: For a function $ f:A \rightarrow B $ , $ \{ (x,f(x)) : x \in A \} $ is the graph of the function $ f $.

Graph [ with no loops, not directed, not weighted ] is a mathematical object of the format $ G = <V,E> $ , where $ V $ is set of vertices, and $ E $ is a set of edges between vertices and is defined as $ E = \{ \{u,v\} : u,v \in V \} $

Question: What is the relation between 'Graph' as defined in graph theory and 'Graph of function' as defined above? It seems to me that the definition for graph of a function is some sort of set of edges ( and the vertices are $x \in A $? ), but I want to be sure.

1

There are 1 best solutions below

0
On BEST ANSWER

Briefly, "yes", the questioner is perfectly correct. In more detail:

A Directed Graph, in the sense of vertices and edges, provided we agree to allow loops is exactly the same as a subset of the cartesian product $V \times V$ where $V$ is the set of vertices. The same structure is also called a binary relation on $V$.

Some graphs in that sense are functions from $V$ to $V$. These are the special graphs where for every $v \in V$ there is exactly one edge $(v,w)$ in the graph for some $w \in V$.

When the graph of a function $f: \mathbb{R} \to \mathbb{R}$ is drawn, the points in the drawing (on the curve of the function) are all coordinate points in the plane $\mathbb{R} \times \mathbb{R}$.

A function $f: \mathbb{R} \to \mathbb{R}$ can always be thought of as a set of ordered pairs $$\{(x,y) \in \mathbb{R} \times \mathbb{R} \mid y = f(x)\}.$$ From this viewpoint the "graph of a function" is just a special case of a "directed graph" as in graph theory where the vertices are all the elements of $\mathbb{R}$ and the edges are all the pairs $(x, f(x))$. So an edge of the graph is a point in the plane.

This story still works for functions which are multivalued, partial, or are not from $\mathbb{R}$ to $\mathbb{R}$, etc.

If you think about the adjacency matrix of a graph on a finite set of vertices, you have exactly the same underlying idea as plotting the graph of a function. The places you put a $1$ (for the existence of an edge) in the matrix are points being selected as part of the plot. In the case of the adjacency matrix it's a discrete space rather than the dense real plane, but the graph in each case is determined by picking out points in a space with two axes along which the set of vertices is laid out.