[Python] counting unique isomorphic embeddings in a complete dual tree

The problem of counting and generating unique isomorphic embeddings of a graph into a full binary tree with a given number of edges


I faced the problem of counting and, ideally, generating unique isomorphic embeddings of some graph into a full binary tree. I know that these embeddings satisfy the following condition: the number of edges in the embedded graph must be equal to the depth of the full binary tree (n).

Based on manual counting, I determined the number of such embeddings for small values of n:

• For a full binary tree of depth n = 2: there are 2 unique isomorphic embeddings.
• For a full binary tree of depth n = 3: there are 5 unique isomorphic embeddings.
• For a full binary tree of depth n = 4: there are 16 unique isomorphic embeddings.

Here is an example visualization of what "shapes" I am trying to find in a binary tree:

Here's an example of visualizing what "shapes" I'm trying to find in a binary tree:

In solving this problem, I tried to use the recurrence relation f(n) = 4f(n-1) - 2f(n-2) with initial conditions f(2) = 2 and f(3) = 5, since it numerically matched my hand calculations for small n. However, while this relation gave the expected number of embeddings (f(2) = 2, f(3) = 5, f(4) = 16), the recurrence relation itself does not provide explicit instructions or rules on how exactly these embeddings should be constructed.

My further attempts included analyzing the visualization for n=4 to identify patterns in the nesting structure and developing heuristic rules for their generation. However, these rules turned out to be special cases and could not provide correct results for n=3 without manual adjustment, and for n > 4 they remained completely undefined.

I need to know how many isomorphic embeddings there will be for n = 5 and 6. And also adjusting the visualization of the construction of trees and embeddings

Here are my efforts in the form of Python code, where I also tried to visualize the tree and the generated "passages":

import networkx as nx
import matplotlib.pyplot as plt
from collections import defaultdict, deque
import math
import ipywidgets as widgets
from ipywidgets import interact, interactive, fixed, interact_manual
from IPython.display import display, clear_output
import itertools

print("Библиотеки импортированы.")

def get_children(node_id):
return [node_id + 'L', node_id + 'R']

def get_parent(node_id):
if len(node_id) > 1:
return node_id[:-1]
else:
return None

def get_node_depth(node_id):
return len(node_id) - 1

def get_tree_layout(nodes):
pos = {}
max_depth = 0
nodes_at_depth = defaultdict(list)
for node in nodes:
depth = get_node_depth(node)
nodes_at_depth.setdefault(depth, []).append(node)
max_depth = max(max_depth, depth)
for depth in nodes_at_depth:
nodes_at_depth.setdefault(depth, []).sort(key=lambda x: (len(x), x))
for depth in range(max_depth + 1):
nodes_on_level = nodes_at_depth.get(depth, [])
num_nodes = len(nodes_on_level)
level_width = 2.0 ** (max_depth - depth + 1)
if num_nodes > 1:
x_coords = [i * (level_width / (num_nodes - 1)) - level_width / 2.0 for i in range(num_nodes)]
else:
x_coords = [0]
for i, node in enumerate(nodes_on_level):
pos.setdefault(node, (x_coords , -depth))
return pos

print("Вспомогательные функции определены.")

def generate_special_walks(n):
if n < 2:
print(f"Ошибка: Глубина n={n} должна быть >= 2.")
return None

walks = []
target_depth = n - 1

simple_paths = []
queue = deque([['0']])
while queue:
current_path = queue.popleft()
last_node = current_path[-1]
current_depth = get_node_depth(last_node)
if current_depth == target_depth:
simple_paths.append(current_path)
continue
if current_depth < target_depth:
children = get_children(last_node)
for child in children:
new_path = current_path + [child]
queue.append(new_path)
walks.extend(simple_paths)

if n == 2:
pass

elif n == 3:
walks.append(['0', '0L', '0', '0R', '0RL'])
print("Предупреждение: Для n=3 сгенерировано 4 простых пути + 1 'обходной' путь (0->L->0->R->RL) "
"для соответствия f(3)=5. Структура 5-го пути является предположением.")

elif n == 4:
nodes_depth1 = ['0L', '0R']
for p_node in nodes_depth1:
children_p = get_children(p_node)
c1_node = children_p [0]
c2_node = children_p [1]
leaves_under_c2 = get_children(c2_node)
for l2_node in leaves_under_c2:
walks.append(['0', p_node, c1_node, p_node, c2_node, l2_node])
leaves_under_c1 = get_children(c1_node)
for l1_node in leaves_under_c1:
walks.append(['0', p_node, c2_node, p_node, c1_node, l1_node])

else:
print(f"Предупреждение: Точное правило генерации {original_f_n.get(n, '?')} 'проходок' для n={n} неизвестно.")
print("Будут показаны только простые пути до листьев.")
return simple_paths

walks.sort(key=lambda x: (len(x), str(x)))
return walks

original_f_n = {2: 2, 3: 5, 4: 16, 5: 54, 6: 184}

print("Функция генерации 'проходок' 'generate_special_walks' определена.")

def visualize_walk(base_G, pos, walk, index, total_walks_count, n_depth_param):
num_steps = len(walk) - 1
walk_str = ' -> '.join(walk)
max_len = 80
if len(walk_str) > max_len:
walk_str = walk_str[:max_len-3] + "..."

plt.figure(figsize=(10, 6))
title = (f"Проходка {index+1}/{total_walks_count} для n={n_depth_param}\n{walk_str}")
plt.title(title, fontsize=9)

nx.draw_networkx_nodes(base_G, pos, node_size=250, node_color='lightgray', alpha=0.7)
nx.draw_networkx_edges(base_G, pos, width=1, edge_color='lightgray', alpha=0.5)
nx.draw_networkx_labels(base_G, pos, font_size=7, font_color='dimgray')

nx.draw_networkx_nodes(base_G, pos, nodelist=walk, node_size=300, node_color='skyblue')
if walk:
nx.draw_networkx_nodes(base_G, pos, nodelist=[walk [0]], node_size=400, node_color='red')
if len(walk) > 1:
nx.draw_networkx_nodes(base_G, pos, nodelist=[walk [-1]], node_size=400, node_color='darkgreen')

walk_edges_viz = []
edge_colors = []
edge_styles = []
edge_counts = defaultdict(int)
for j in range(num_steps):
u, v = tuple(sorted((walk [j], walk [j+1])))
edge_key = (u, v)

if base_G.has_edge(walk [j], walk [j+1]):
walk_edges_viz.append((walk [j], walk [j+1]))
if get_parent(walk [j+1]) == walk [j]: edge_colors.append('blue')
else: edge_colors.append('orange')
edge_counts [edge_key] += 1
edge_styles.append('dashed' if edge_counts [edge_key] > 1 else 'solid')

nx.draw_networkx_edges(base_G, pos,
edgelist=walk_edges_viz,
width=2.0,
edge_color=edge_colors,
style=edge_styles)

plt.axis('off')
plt.tight_layout()
plt.show()

print("Функция визуализации 'visualize_walk' определена.")

style = {'description_width': 'initial'}

depth_slider = widgets.IntSlider(
value=4, min=2, max=6, step=1,
description='Глубина дерева n (уровни 0..n-1):',
style=style, layout=widgets.Layout(width='50%')
)

max_plots_slider = widgets.IntSlider(
value=16, min=1, max=50, step=1,
description='Макс. число визуализаций для показа:',
style=style, layout=widgets.Layout(width='50%')
)

run_button = widgets.Button(
description="Сгенерировать и показать 'проходки'",
button_style='success',
tooltip='Нажмите для запуска генерации и визуализации',
icon='check'
)

output_area = widgets.Output()

def run_special_walk_generation(b):
with output_area:
clear_output(wait=True)
print("Запуск...")

n_depth = depth_slider.value
max_plots = max_plots_slider.value
target_level = n_depth - 1

print(f"Параметры: Глубина дерева n = {n_depth}")

print("\nГенерация 'проходок'...")
global original_f_n
walks = generate_special_walks(n_depth)

if walks is None:
print(f"Не удалось сгенерировать проходки для n={n_depth}.")
return

num_walks = len(walks)
print(f"Сгенерировано {num_walks} 'проходок'.")

if n_depth in original_f_n:
print(f"\nСравнение с вашей целевой последовательностью f(n):")
print(f" Для n={n_depth}, целевое значение f({n_depth}) = {original_f_n [n_depth]}.")
print(f" Текущий код сгенерировал {num_walks} 'проходок'.")
if original_f_n [n_depth] == num_walks:
print(" => Количество совпадает.")
else:
print(" => Количество НЕ совпадает!")
else:
print(f"\nЦелевое значение f({n_depth}) неизвестно для сравнения.")
print("-----------------------------------------------------")

if not walks:
print("Нет 'проходок' для визуализации.")
return

print("\nПодготовка графа для визуализации...")
all_nodes_in_walks = set()
for walk in walks:
all_nodes_in_walks.update(walk)

max_d = 0
for node in all_nodes_in_walks:
max_d = max(max_d, get_node_depth(node))

nodes_to_include = set(['0'])
for d in range(max_d + 1):
level_nodes = ['0' + ''.join(p) for p in itertools.product('LR', repeat=d)] if d > 0 else ['0']
nodes_to_include.update(level_nodes)

nodes_to_include.update(all_nodes_in_walks)

base_G = nx.Graph()
base_G.add_nodes_from(list(nodes_to_include))
for node in nodes_to_include:
parent = get_parent(node)
if parent is not None and parent in nodes_to_include:
base_G.add_edge(parent, node)

pos = get_tree_layout(nodes_to_include)
print(f"Базовый граф содержит {len(nodes_to_include)} узлов и {base_G.number_of_edges()} ребер.")

print(f"\nВизуализация первых {min(num_walks, max_plots)} из {num_walks} 'проходок'...")
if num_walks > max_plots:
print(f"(Остальные {num_walks - max_plots} не показаны согласно настройке)")

for i, walk in enumerate(walks):
if i >= max_plots:
break
visualize_walk(base_G, pos, walk, i, num_walks, n_depth)
print("\nВизуализация завершена.")

print("--- Интерактивный интерфейс для генерации 'проходок' ---")
print("Задайте глубину дерева n и нажмите кнопку:")
display(depth_slider)
display(max_plots_slider)
display(run_button)
display(output_area)

run_button.on_click(run_special_walk_generation)

Continue reading...