ReaLNero's blog

The tree that isn't a tree
By ReaLNero, 7 years ago, In English

The recurrence

f(i, i) = 0

f(i, j) = g(f(i, j - 1), f(i + 1, j)) + cost(i, j)

for any function g and cost (minimum and (i + j), respectively, for example) generates a family of graphs that (informally) look like a complete binary tree that cuts into itself.

Has this family of graphs been named? Does it have properties that could be useful in competitive programming?

Notable things:

  • The graphs have no Euler path nor circuit for depths larger than 2.

  • Maximal independent set is taking the last depth, third last depth, etc.

  • Seems like Hamiltonian paths don't exist for larger depths.

  • Hamiltonian circuits definitely don't exist, since there are vertices with degree 1.

  • Odd cycles don't seem to exist, which means the graphs are bipartite

Screenshot courtesy of VisuAlgo

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

"Pascal triangle thingy"

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Corners of square grid:

* - * - * - * - *
|   |   |   |
* - * - * - *
|   |   |
* - * - *
|   |
* - *
|
*
→ Reply