Will encoding affect computability?
As long as there's a computable mapping between the two encodings, changing from one to the other won't affect computability, since computable functions compose. If there isn't a computable mapping between the encodings, you can't effectively use at least one of them, since there's no way to figure out what the encoding of your input should be in that scheme. (For example, suppose you come up with a coding of graphs that isn't computably translatable from the adjacency matrix. How would you use that encoding? If I give you a graph, you can't figure out what string encodes it.)