Comparing Alternative Trees, Alphabets, and Gate Systems

1. Framing the Problem: Many Trees, Many Alphabets

2. Model Families: Graphs, Labelings, and Rules

3. Concrete Example: Two Competing 10-Node Trees

4. Equivalence, Isomorphism, and Invariants

5. Hands-On: Spotting Invariants and Differences

Try this thought exercise. You do not need to draw perfectly; rough sketches are fine.

Task A: Two Trees on Paper

1. On a sheet of paper, draw Tree A:

• 10 nodes in 4 layers (1 at top, 10 at bottom).
• Connect each node in layer i to 2 or 3 nodes in layer i+1 so that you have 22 edges total.

1. On another sheet, draw Tree B:

• Same 10 nodes and layers.
• Rearrange edges so some nodes have degree 4 and some have degree 1, but still 22 edges.

Now answer for yourself:

• Q1: Do Trees A and B have the same number of nodes? (Yes/no)
• Q2: Do they have the same number of edges? (Yes/no)
• Q3: Does every node in Tree A have the same degree as some node in Tree B? (Compare degree sequences.)
• Q4: Pick the top node and bottom node. Count the number of distinct shortest paths between them in each Tree.

Task B: Simple Letter Labeling

1. Take Tree A and label its 22 edges with the 22 Hebrew letters in any order.
2. Create Model A1: your first labeling.
3. Create Model A2: a second labeling where you permute the letters (e.g., shift every letter one step along the alphabet).

Reflect:

• Are A1 and A2 isomorphic as unlabeled graphs? (Yes: they have identical edges.)
• Are they isomorphic as labeled graphs? (Only if your permutation respects labels.)
• What invariants stay the same when you change labels? (Hint: node degrees, distances.)

Use this to get a feel for how much variety comes from connectivity vs labeling.

6. Minimal Coding: Comparing Two Tiny Gate Systems

You can use simple code to compare alternative gate systems as constraint networks.

Below is Python-like pseudocode (works in standard Python 3 with `networkx` installed, but you can also just read it conceptually).

The idea:

• We define a tiny alphabet of 3 letters: A, B, C.
• We define two gate systems:
• System 1: all ordered pairs except repeats.
• System 2: only pairs where the second letter is later in the alphabet.
• We then compare how many gates and how much branching each system allows.

```python

import itertools

letters = ["A", "B", "C"]

System 1: all ordered pairs (x, y) with x != y

gates1 = [(x, y) for x, y in itertools.product(letters, repeat=2) if x != y]

System 2: only pairs where y comes later in the alphabet than x

order_index = {ch: i for i, ch in enumerate(letters)}

gates2 = [

(x, y) for x, y in itertools.product(letters, repeat=2)

if orderindex[y] > orderindex[x]

]

print("System 1 gates:", gates1)

print("System 2 gates:", gates2)

Simple statistics

print("System 1: number of gates =", len(gates1))

print("System 2: number of gates =", len(gates2))

Branching factor: how many outgoing gates from each letter?

from collections import Counter

out1 = Counter(x for x, y in gates1)

out2 = Counter(x for x, y in gates2)

print("System 1 outgoing:", out1)

print("System 2 outgoing:", out2)

```

What you should notice (even without running the code):

• System 1 allows more total gates than System 2.
• In System 2, some letters may have fewer or no outgoing gates.

This is analogous to comparing two letter-gate systems on a Tree:

• Same alphabet, different combinatorial rules.
• You can measure differences in expressive power (how many sequences are possible) and information flow (how many options at each step).

7. Evaluating Models: Textual, Mathematical, Expressive

8. Quick Check: Isomorphism and Evaluation

Test your understanding of isomorphism and model evaluation.

9. Mini Project: Define and Compare Your Own Family

Spend a few minutes sketching your own mini family of models.

Step 1: Fix a base graph

• Choose 6–8 nodes.
• Connect them with 8–10 edges so that the graph is connected.

Step 2: Define two labelings

• Pick an alphabet of 8–10 symbols (letters, numbers, or shapes).
• Model 1: assign symbols to edges in any order.
• Model 2: reassign symbols so that at least one node has only high-valued symbols (e.g., later letters) on its edges.

Step 3: Add a simple gate rule

• For both models, define a rule such as:
• "A valid walk must always move to a node with a symbol that is later in the alphabet than the previous edge's symbol."

Step 4: Compare

For each model, answer:

1. How many valid 3-step walks exist from a chosen start node?
2. Which nodes act as bottlenecks (few outgoing valid moves)?
3. Which invariants are shared (e.g., node degrees, distances)?
4. Which properties differ because of labeling and gate rules (e.g., reachable nodes under the constraint)?

Write a 2–3 sentence summary:

• "Model 1 and Model 2 share the same graph but differ in labeling. Under my gate rule, Model 2 concentrates valid walks near node X, while Model 1 spreads them more evenly."

10. Key Term Review

Use these flashcards to reinforce core concepts from the module.