How to draw a Bethe lattice with a given number of nodes N and coordination number z?

How to draw a Bethe lattice with a given number of nodes N and coordination number (number of connections), z?

Reference: https://en.wikipedia.org/wiki/Bethe_lattice

Answer 1

[Ravi]

Hi Nadatimuj,

I understand that you want to draw a Bethe lattice for a given number of nodes and coordination number.

A Bethe lattice is an undirected acyclic graph in which every node except the ones on the last level are connected to “z” other nodes.

Please note that the number of nodes in level “l” are given by z(z – 1)^(l – 1), assuming the level starts at 1 and not counting the the root node as a level.

Please find the below code that plots the Bethe lattice.

n = input('enter number of vertices(n):');
z = input('enter coordination number(z):');
A = zeros(n, n);

% Assign root node edges
for i = 1:z
    A(1, i + 1) = 1;
    A(i + 1, 1) = 1;
end

level = 2;
parent = 2;
current_node = z + 2;
while current_node <= n
    nodes_in_level = z * (z - 1) ^ (level - 1);
    number_of_children = 0;
    for i = 1 : nodes_in_level
        A(parent, current_node) = 1;
        A(current_node, parent) = 1;
        current_node = current_node + 1;
        number_of_children = number_of_children + 1;
        if current_node > n
            % if number of nodes exceed n,
            % then terminate the process
            break
        end
        if number_of_children == z - 1
            % if number of children for a parent are filled,
            % move to the next parent node
            parent = parent + 1;
            number_of_children = 0;
        end
    end
end

% Create a graph object
G = graph(A);

% Plot the graph
plot(G, 'Layout', 'force'); % You can choose different layouts

% Add a title
title('Bethe lattice');    

Hope this solution helps.

Thanks,

Ravi Chandra