Turing Machines and Graphs Homework

  1. Revisit example 3.23 in the book, which discusses a string encoding for an undirected graph. What, if anything, would be different if we want to encode a directed graph instead?
  2. Let \(L = \{\langle G \rangle | G\) is a directed graph and no node in \(G\) has more than 1 outgoing edge.\(\}\). Is \(L\) decidable? If so, give a high level description of a Turing machine that decides \(L\). If not, explain why not.