Please answer the quesiton (a). PROBLEM 1: GRAPH ENCODINGS Let G(V) denote the u
ID: 3800505 • Letter: P
Question
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 graphExplanation / Answer
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