Graphy Theory Thread

How in the fuck does one connect each color to itself while going over every dot? Is there math for this?

retard pseudo-math for retard cs shitters

>math
bitch you're connecting dots tf do you mean a "math"?

Start at lower blue, connect to upper blue, then upper pink to lower pink then left turquoise to right turq then lower yellow to upper yellow to upper green to lower green to lower orange to upper orange.

But yes, this is graph theory. What you'd want to do is simply figure out what this problem represents as a graph in abstract terms, then look up whether the process you want to do is possible.

Remember that autism test where you have to connect the houses to the supplies. That's K(3,3) and it's not planar. Hence the problem cannot be done. Once you realise it's K(3,3), some smart guy already proved it's not planar, so you don't have to sit around for hours trying to make it work.

In this case, however, I just saw the solution.

>while going over every dot
figures """"discrete math""""lets can't read

I thought they were just placeholders and did not interpret the question correctly.

On topic, here is a solution if you're allowed to move diagonally across a square. Start at top orange.

It has to be done without moving diagonally though. I've spent two days on this.

Turn in your computer if you hate CS so much. Oh what's that? You're a hypocrite who parrots other people's opinions to try and fit in? Carry on.

Without diagonals, I'd say it was impossible (though I can't prove it). The positioning of the pink and orange on the rim causes the problems. To actually prove it would be an exercise in graph theory.

Maybe you could show that ANY way of connecting orange to orange prevents you from connecting the other colours.

I also wonder if there is a computational analyser that could just brute force it.

Took me 5 minutes, easy as fuck. There are some lines that logically have to be made and then once you make them the solution is pretty clear if you want to fill up the entire space.

Is the 7 bridges problem impossible for any odd number of bridges?

>retard pseudo-math
Not is actually interesting, the problem is that it is usually a course for CS people aka. brainlets for whom the Idea of a "proof" is too difficult to comprehend.

This is a fucking kids puzzle
> muh computational analyser

How are you generalizing the problem? If the 7 bridges in Konigsberg had been arranged differently the problem would have been solvable.

Every vertex has to have an even number of edges so it depends on how you connect them.

this is that fucking app Flow or something

Give an arrangement of the 7 bridges that would make the problem solvable.

Never mind, I found one immediately after posting. Carry on.

It's not every vertex, it's just that at least one has to have an even number of edges.

Trivial

No, if you want to end up where you started you need an even number of edges for every vertex, if you don't care where you end up 2 vertices can have an odd number of edges.

why do computer science retards and physics virgins love to find the most trifling puzzles that exist and present them as interesting mathematical problems?

What makes it even more trivial is the fact that you could just write a troglodyte program that would just brute force this so why the fuck are you even asking the question? You aren't going to try to reason the answer out of it because you're presumably too stupid (which is why you took CS).

As for the physics idiots: stick to experimenting and waffling about planck lengths whenever anything to do with the infinite is discussed.

Solved it.

>using a computer to complain about people who make your computer run
I'm sure the irony is not lost on you.

hey i have this game on steam

>What makes it even more trivial is the fact that you could just write a troglodyte program that would just brute force this
what's the algorithm?

Max flow

How does that get the "going over every dot" part? Remember, existence of a Hamilton path in a general graph is NP-complete, if I recall correctly.

With max cost
Remember, dont say dumb unrelated things

Sorry, you dont even need min cost, max flow is enough. Check out the 2017 latin america ICPC regional, problem K. Bipartite matching is a simple solution.