MathPlotAI Logo MathPlotAI

Puzzletown: A Geometric Example of Minimum Dominating Sets

Puzzletown: A Geometric Example of Minimum Dominating Sets
Loading the math board and drawing, please wait…
2021-01-28 03:23
CircleVectorOptimizationGeometric ConstructionGraphing
This GeoGebra example demonstrates how to find a minimum dominating set on a planar graph-like configuration by selecting points so that every point is either chosen or is adjacent to a chosen one. It focuses on the core ideas of dominating sets in graph theory and the optimization goal of minimizing the number of selected vertices. The construction uses geometric primitives—Segment and Circle—to lay out the points and connections (e.g., segments such as AB, DE, JK, LM, MN together with circular/planar regions). It also employs CountIf to count how well a candidate selection covers all vertices via neighborhood relations. Key objects include the point set (A through N), boolean/flag-style selection markers (AisCart, BisCart, …) and neighbor-coverage indicators (AisNeighbour, BisNeighbour, …), enabling interactive evaluation of candidate solutions. Suitable for upper-secondary and undergraduate introductory lessons on optimization, graph concepts, and visualization-based reasoning.

GeoGebra Commands & Parameters

  1. Segment(A, B) → AB
  2. Segment(D, E) → DE
  3. Segment(J, K) → JK
  4. Segment(L, M) → LM
  5. Segment(M, N) → MN
  6. CountIf(x ≟ true, listOfCarts) → numCarts
  7. Circle(A, 0.35) → borderA
  8. Circle(B, 0.35) → borderB
  9. Circle(C, 0.35) → borderC
  10. Circle(D, 0.35) → borderD
  11. Circle(E, 0.35) → borderE
  12. Circle(F, 0.35) → borderF
  13. Circle(G, 0.35) → borderG
  14. Circle(H, 0.35) → borderH
  15. Circle(I, 0.35) → borderI
  16. Circle(J, 0.35) → borderJ
  17. Circle(K, 0.35) → borderK
  18. Circle(L, 0.35) → borderL
  19. Circle(M, 0.35) → borderM
  20. Circle(N, 0.35) → borderN
  21. Circle(A, 0.35) → fillA
  22. Circle(B, 0.35) → fillB
  23. Circle(C, 0.35) → fillC
  24. Circle(D, 0.35) → fillD
  25. Circle(E, 0.35) → fillE
  26. Circle(F, 0.35) → fillF
  27. Circle(G, 0.35) → fillG
  28. Circle(H, 0.35) → fillH
  29. Circle(I, 0.35) → fillI
  30. Circle(J, 0.35) → fillJ
  31. Circle(K, 0.35) → fillK
  32. Circle(L, 0.35) → fillL
  33. Circle(M, 0.35) → fillM
  34. Circle(N, 0.35) → fillN
  35. Segment(A, I) → AI
  36. Segment(A, H) → AH
  37. Segment(B, C) → BC
  38. Segment(B, J) → BJ
  39. Segment(C, D) → CD
  40. Segment(D, K) → DK
  41. Segment(E, F) → EF
  42. Segment(E, L) → EL
  43. Segment(F, G) → FG
  44. Segment(F, M) → FM
  45. Segment(G, H) → GH
  46. Segment(G, N) → GN
  47. Segment(H, N) → HN
  48. Segment(I, J) → IJ
  49. Segment(I, N) → IN
  50. Segment(K, L) → KL

AI Drawing Prompt Reference

Draw a planar graph-like configuration with fourteen points arranged in clusters, connected by straight segments to form a network. Around each point, place a small circle as a marker. Connect certain pairs of points with lines to show adjacency, such as linking points in a chain or ring. Use distinct colors or fills to indicate selected versus unselected points, making the coverage relationships visually clear. The layout should emphasize the neighborhood structure for evaluating a dominating set.
The prompt above was compiled from the original drawing commands and is for reference only.