http://www.newgrounds.com/portal/view/655010
What kind of mathematics, if any, provides a systematic way to solve problems like the game above?
(Pic related?)
Graph theory basicly. These problems are often linked to computer sience though, with algorithms like depth-first search and width-first search
>>7659927
https://en.wikipedia.org/wiki/Knot_Theory
>>7659927
graph theory. Look at planarity of a graphs and elementary counterexamples (K5, graphs having K5 as a subgraph)
I play with feelings. I at lvl 8 atm :^)
Prop 65 Warning:
This activity may contain a problem known to the state of California to be unsolvable by the means of the greedy algorithm.
>>7659961
>width-first search
At least know the proper terminology if you're going to be a pop-comp-scientist
topological graph theory to be precise
Is that e really needed?
>>7660247
define needed
loops are important sometimes
>>7659962
lol no
>>7660236
This is the correct answer.
The one with bridges and rivers and shit
>>7660292
yes
>>7660155
Might be he has a different native language and translated it directly
>>7659927
There are linear-time planarity testing algorithms. I think some of them might also give you a planar embedding as output (probably as a rotation system)
https://en.wikipedia.org/wiki/Planarity_testing#Algorithms
although if you want to do it by hand it's a bit different.
As some quick heuristics you could do some basic checks like..
If the graph has no triangles, then m <= 2n - 4 and in general m <= 3n - 6 where n = number of vertices and m = number of edges. If your graph doesn't satisfy those, then it's impossible to solve.
if you aren't sure whether it's possible - if you are, just run one of those algorithms on the wiki article I guess.
Wouldn't it be a good idea to find some holes (induced cycles) as the outer plane? I mean you know that in a planar embedding that those have to form regions.
I mean you might end up with less space to work with since you might choose a C_3 as your outer face since those are easy to find induced cycles...
actually scratch that, you wouldn't want induced cycles, you'd want cycles without any paths or chords... so I guess you can't really guarantee much besides triangles without already knowing how it's gonna be embedded?
Okay. Would a good strategy be to find a triangle in the graph with vertices of the highest possible degree, then to just continue to find adjacent triangles to those and embed those close to the edges? Since any C_3 in a graph is going to have to be its own region. I'm on the 4th last level so far by going through a strategy similar to this.
The last level is not possible, is it?
Unless I counted wrong the degree sequence is:
5, 6, 5, 5, 5, 6, 6, 9, 5, 9, 5, 9, 5, 5, 5, 9, 6, 7, 7, 6, 7, 8, 7, 7, 6, 9, 7, 5, 5, 5, 9, 6, 5, 9, 9, 5, 9, 5, 9, 5, 5, 9, 6, 9, 6, 6, 9, 9, 5, 9, 9, 8
which means |V| = 52 and |E| = 176, which violates |E| <= 3|V| - 6
it also violates some other properties regarding vertex degrees of planar graph, in particular the amount of degree <6 vertices with respect to degree >6 vertices.
I mean, maybe i just miscounted or something... but it's pretty far off from meeting those.
giving a non-planar graph for the last level is pretty evil though, so it would make sense...
>>7659927
I feel like I was nerd snipped
>>7660269
Why would you use it in this case?
>>7661942
I just beat it.
>>7661942
Disregard that, I was counting the closed neighborhoods instead of the open neighborhood, so I guess subtract 1 from each of those degrees. Oops.
>>7661951
see >>7661996
I just beat it too. It was actually easier than the last couple levels since you could just orient a K_3 and then orient other K_3s along the sides of the triangle since the graph was very dense (for a planar graph).
>>7659927
If pic is related then I remember seeing that in the MIT statistics/probability lectures.
FUCK YOU FUCK YOU FUCK YOU WHY DID I START THIS FUCKING SHIT YOU FUCKING FUCK FUCKER
This is where I became too tired.
Basically the strategy is to start with one large triangle and keep putting the nodes one-by-one in place.
>>7659927
Judging by the picture, it looks like it'll have something to do with Graphs and combinatorics.
>>7661063
Really basic knot theory since the lines are all straight. Planar graph theory would be better.
>>7660155
nigga
