Solution To MAT310 Test[Discrete Mathematics]

Solution to MAT310 C.A Test

(1a).  Let $R$ be a relation defined on the vertex set of a graph $G$ by $URV$, whenever $U,U\in{V(G)}$. Show that $R$ is an equivalence relation.

(b).  Ten lecture schedules denoted as $t_1,t_2,...,t_{10}$ are assigned to some $300$ level courses such that $C_1=\{t_1,t_2,t_3\}, C_2=\{t_1,t_3,t_4,t_5\}, C_3=\{t_2,t_5,t_6,t_7\}, C_4=\{t_4,t_7,t_8,t_9\}, C_5=\{t_2,t_6,t_7\}, C_6=\{t_8,t_9,t_{10}\},\ \text{and}\ C_7=\{t_1,t_3,t_9,t_{10}\}$.

Draw a graph model to illustrate this information given that two courses are joined by an arc if they have a common time schedule.

(2a)  Show that every vertex of $G$ belongs to exactly one component of $G$. Hence show that every edge of $G$ belongs to exactly one component of $G$.

(b)  If $F$ is a field and $f\in{F[x]}$ has degree $n$, then show that $F$ contain at most $n$ root of $f$.

Solution:

(1a)  Since $R$ is a relation defined on the vertex set of a graph $G$ by $URV$ whenever $U,V\in{V(G)}$.

Then we are to show that $R$ is an equivalent relation.

To show this, we know from definition that in an undirected graph, a vertex $v$ is reachable from a vertex $u$ if there is a path from $u$ to $v$, then there is a relation between $u$ and $v$, and the trivial vertex is counted as having a path of length zero. We thus say that $R$ is an equaivalence if the following holds in the graph below:

(i) It is reflexive:There is a trivial path of length zero from any vertex to itself, which exists in the graph.

(ii) Symmetric: If there is a path from $u$ to $v$, the same edges form a path from $v$ to $u$, which holds.

(iii)Transitive: If there is a path from $u$ $v$ and a path from $v$ to $w$, then there is a path from $u$ to $w$, which also holds.

This can be verified by a graph, below is a triangular graph below:

A graph that satsifies equivalence relation.

(b) The lectures can be represented in  a graph like the one below: Remember when drawing a graph, it can be random, it is not necessary for it to look like this, except you  are drawing a special kind of graph like the kuratowski graph, peterson graph and maybe the fibonacci graph.

A graph representing ten lecture schedule.

(2a)   To show this, we need to define a component graph, A graph $G$ is a component graph $c(G)$  if $H\subset{G}$ i.e $H$ is a subgraph of $G$.

Then $H$ is said to be a component of $G$ if:

(i) $H$ is connected

(ii)$H$ is not contained in any connected subgraph of $G$ which has more vertices or edges than $H$.

In the graph below it is evident that $H$ is a connected component of $G$ and for every vertex $v_1\in{G}$ there exists a $u_1\in{H}$ and for every edge $e_1\in{G}$ there exists a $b_1\in{H}$, and hence the number of connected component is $2$.

A connected component graph

(b)  Proof:   Since there is a natural embedding $F[x]\subset{f}$, we may view $f$ as a polynomial in $F$. Since $F$ is a field, then $F$ is a euclidean domain, so the division algorithm applies, and for any $u\in{F}$, we have

                                                          $f(x)=q(x)(x-u)+r$

where $q(x)\in{F(x)}$ and $r\in{F}$ is a constant. If $f(u)=0$, it follows that $r=0$ and $x-u$ divides $f(x)$ in $F(x)$. If $u'\neq{u}$ is another root of $f(x)$ in $F$, since $u'-u\neq{0}$, it follows that $q(u')=0$. continuing by induction on deg$f(x)$, we conclude that

                                          $f(x)=(x-u_1)(x-u_2)...(x-u_m)f_1(x)$

Where $u_1,u_2,...,u_m$ are the distinct roots of $f(x)$ in $F$ and $f_1(x)\in{F[x]}$ has no roots in $F$ except possibly those already listed.

Hence, clearly $m\leq$deg$f(x)$. End of Proof