Please answer the quesiton a PROBLEM 1 GRAPH ENCODINGS Let G

Please answer the quesiton (a).

PROBLEM 1: GRAPH ENCODINGS Let G(V) denote the undirected simple graphs with vertex set Vn t 1, 2 ...,n). Our encoding will be (G) g(Vn) 2\" where the encoding alphabet is Define KG) to be the string consisting of the edges of G in lezicographic order delimited by colons. That is, the edge (1,2) must appear before (1,3) in the encoding, and the edge (1,2) is encoded as 1 2 instead of 2 1. We begin the encoding with in order to easily identify the left end of the tape. (We will not list vertices as we did in lecture.) For example, the graph

Solution

a)

The <G> of the graph is given as follows:

and <G> is in lexicographic order delimited by colons.

$1:2|2:3|2:6|2:7|3:4|3:5