Weekly Notes for Week 23

Week 22 was a free week. In Week 23 we continue with cycle bases, with a focus on de Pina’s algorithm and applications of minimum cycle bases in chemical graph invariants.

• This week’s topics:

  • Minimum cycle bases and the de Pina construction.
  • Witness sets and the shortest odd-intersection cycle subproblem.
  • The parity-lift construction for shortest odd-intersection cycles.
  • Applications of minimum cycle bases, in particular the Berger–Gritzmann–de Vries invariant.

• Interactive material:

  • MCB visualizer for de Pina and Horton on the exercise graph.
  • Parity lift visualizer for the shortest odd-intersection cycle subroutine.

• Reading material:

  • Mandatory: Berger, Gritzmann, and de Vries, Minimum Cycle Bases and Their Applications, Section 3.2.
  • Recommended background: de Pina runtime / minimum cycle bases article.
  • Background from Week 21: Counterexamples in Chemical Ring Perception.

• Slides and notes:

  • Horton / de Pina / minimum cycle bases
  • Additional cycle-basis slides
  • Ring-perception notes
  • Berger–Gritzmann–de Vries Cycle Invariants: worked examples

• Exercises:

  • Exercise Sheet 05
  • No solution sheet is published for Exercise Sheet 05.