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
Part 3 - K5 and K3,3 by Brian Smith)
I just thought of this: if 2-10-5-15 is a valid connection of 2 to 15, then so would be 2-10-1-14. Then also range 1 - 5 would be also non-planar since all five would be mutually connected through the 1. That would limit it to 1-4.
But clearly it's possible to form a planar graph of 1-5. Indirect connection can't be a disqualification.
Edited on August 18, 2021, 6:02 pm
|
|
Posted by Charlie
on 2021-08-18 17:54:04 |
re: Part 3 - K5 and K3,3
