A factor graph is a graph where each node is numbered and if x is a factor of y, then x and y are connected. A graph is planar if it can be drawn on paper with no lines crossing.
1) Create a planar factor graph with nodes numbered from 2 through 23.
2a) [easy] Show that no planar factor graph is possible with nodes numbered 2 through 32.
2b) [hard] Show that no planar factor graph is possible with nodes numbered 2 through 24.
3) If the nodes are numbered 1 though n, find the largest planar factor graph and prove that n+1 is impossible.
Tip: A finite graph is planar if and only if it does not contain as a subgraph either the complete graph K5 or the complete bipartite graph K3,3.
(In reply to
re: Setting an upper limit for 3 by Charlie)
highNumber=16;
numbers=[1:highNumber];
setsOf5=nchoosek(numbers,5);
for i=1:length(setsOf5)
k5=true;
setOf5=setsOf5(i,:);
for j=1:4
for k=j+1:5
if connected(setOf5(j),setOf5(k))==false
k5=false;
break
end
end
if k5==false
break
end
end
if k5
disp('k5')
disp(setOf5)
end
end
setsOf3=nchoosek(numbers,3);
comb=length(setsOf3);
ptrs=[1:comb];
for i=1:comb-1
for j=i+1:comb
s1=ptrs(i); s2=ptrs(j);
set1=setsOf3(s1,:);
set2=setsOf3(s2,:);
k33=true;
for k=1:3
for l=1:3
if connected(set1(k),set2(l))==false
k33=false;
break
end
end
if k33==false
break
end
end
if k33
disp('k3,3')
disp(set1)
disp(set2)
end
end
end
function c=connected(n1,n2)
m=max([n1,n2]); n=min([n1,n2]);
if mod(m,n)==0 && m~=n
c=true;
else
c=false;
end
end
With highNumber = 16 the program does find both a K(5) and a K(3,3):
k5
1 2 4 8 16
k3,3
1 2 4
8 12 16
With highNumber = 15, neither type of K is found.
So the maximum is in fact 15.
Edited on August 17, 2021, 11:59 am
|
|
Posted by Charlie
on 2021-08-17 11:50:07 |
part 3 by computer
