Answer to Question #174437 in Discrete Mathematics for Michael

Question

Define a relation  on the set S of all strings of letters: two strings are related if you can get one from the other by reversing one pair of adjacent letters. For example, cow  ocw

 but cow  woc.

Answer 1

A relation $\rightleftharpoons$ is defined on the set S of all strings of letters: two strings are related if we can get one string from the other by reversing one pair of adjacent letters.

Consider the letters c, a, and t. The set S of all strings of these three letters is given below.

A relation on a set S is a subset of $S \times S$ . If R is a relation on S, we say that “a is related to b” if $(a,b) \in R$ , and is written as a R b. The pair of strings from set S that represent the $\rightleftharpoons$ relation are (cat, cta), (cat, act), (atc, act), (atc, tac), (tca, tac), and (tca, cta). So, the relation R on S is the set {(cat, cta), (cat, act), (atc, act), (atc, tac), (tca, tac), (tca, cta)}.

Note that a relation R is symmetric if it has the property that x R y if and only if y R x. The relation R on S is symmetric because for any $x,y \in S$ , x R y $\Leftrightarrow$ y R x. For example, cat R cta $\Leftrightarrow$ cta R cat.

Since the relation R is symmetric on X, the associated graph is undirected. Draw the graph using the vertex-set as {cat, atc, tca, cta, tac, act} and the edge-set as as shown below.