Venice Bridge challenge

Is it possible to cross all bridges in Venice once, but only once in one single walk?
(except Giudecca of course)

I think it’s possible if there are no more then two island conected by only one bridge…am I missing somthing?

The condition is that either:

[ul]
[li]All islands connect to an even number of bridges.[/li][li]All but two islands connect to an even number of bridges (the other two having an odd number).[/li][/ul]

The simple reason is that every time your path goes to and then leaves an island, it “consumes” two bridges – one to get on, and one to get off. If you ever have an island with only one bridge, and you are not currently on it, once you do get on it, you are stuck. If every island has an even number of bridges this doesn’t happen.

If you have the two odd-numbered islands, you must start one one of those islands and end on the other. Once you leave your starting island, it becomes an even-bridged island, and the other island will eventually become a one-bridged island, blocking you in when you get there.

This is an old mathematicalproblem. Basically any island (or bank) can have either an odd number or an even number of bridges leaving it.

If there are no odd numbers anywhere then you can start anywhere and find a route that crosses all the bridges.

If there are two places that have an odd number of bridge-ends then you must start from one of these and finish at the other.

If there are more odd places then it’s not doable at all.

Note that there must always be an even number of odd places (assuming any bridge connects one place to one other).

Edited to shake fist futilely at leahcim

That’s the theory - there are over 400 bridges in Venice, so the next challenge would be to find the shortest possible route.

Better have a fast computer.

There are plenty of islands that according to google maps have an odd number of bridges, including the Ghetto. It’s just fun trying to find them.

So answer - no.

See the Koenigsberg Bridge problem for more details:

Oh and of course in addition to the odd-even criterion, the graphs have ot be connected. for a traverse to be possible.

Also some bridges in venice correct more then two islands

Not necessarily a problem if it connects A to B and then B to C, but if you have a Y-shaped bridge then things get harder.

If you have a Y-shaped bridge you have a doctrinal problem. You need to decide how to consider it.

Is it 3 distinct bridges representing the three distinct paths between the three islands? Or is it three distinct bridges that meet in a single virtual fourth island at the center? Which fourth island also has to meet our overall problem goals? Or do you consider it to be a conventional 2-ended bridge such that once you use, say, legs a and b, to traverse from island A to B, then the remaining c leg is just a dead end like a pier extending out from island C to nowhere?

Different answers give radically different outcomes.

That third interpretation is the most interesting, since it leads to a fundamentally different sort of problem. If you treat Y-bridges that way, then you have to choose which two legs of the three you’re going to use on your route, and that could change whether the problem is solvable or not. I suspect that if you have enough Y-bridges, the problem of determining whether there’s a solution becomes NP-hard.

I’m not competent to speculate on the NP-ness of any of this. NP always made my head hurt back in CS class :slight_smile:

But yeah, the fun of that last interpretation is that you have 3 different problem graphs to chose from for each Y-bridge in your overall graph. But at the same time, it’s not really *too *labored an interpretation of the basic rule to not re-use a bridge segment.

I shan’t mention X-bridges, not even in passing. :smiley:

A Euler analysis of 400+ bridges would be interesting… :slight_smile:

Ponte dei Tre Ponti is one bridge that connects 5 islands

but the challenge was crossing each bridge once, but no more then once.

Which raises the question as to whether using one entrance to the Ponte, and one of its exits, counts as “crossing” it and makes all of its other points unusable.

If so, you’re then looking at these multi-way bridges and, probably, seeing which of its islands will become even-valency if you discount the Ponte, and which will be odd. Again, if you ever have more than two odd-valency islands then the job is not doable at all.

400 islands? Koenigsberg was hard enough to figure out with just a handful. (Admittedly it gets much easier once you’re standing on Euler’s shoulders) :smiley:

But some of us just enjoy getting lost on Google Maps. Thanks to the OP for suggesting Venice!

How about:

  • Imagine the Y-bridges don’t exist yet. Count the number of odd-order vertices (islands connected by an odd number of bridges).
  • For each place where a Y-bridge will go, the orders of the three adjacent vertices are currently either Even/Even/Even, Even/Even/Odd, EOO, or OOO.
  • If EEE, then choosing a connection between any pair of the vertices will result in EOO, i.e. will add two to the total number of odd vertices.
  • If EEO, you must connect an E and an O, leaving the number of odd vertices unchanged. Otherwise you will have three odd-order vertices.
  • If EOO, you can eliminate the two odd vertices by connecting them, to get EEE, or you can connect two other vertices to leave the total unchanged.
  • If OOO, you connect any two vertices to get OEE.

So, add two to the number of odd vertices for each EEE Y-bridge location, subtract two for each OOO, and subtract two or zero for each EOO. Then check whether the resulting graph(s) would pass the Euler test, i.e. zero or two odd vertices.
If so, for each possible arrangement of Y-bridges, you also have to check that the resulting graph is connected. I don’t think that checking that a graph is connected is NP-hard?

It occurs to me that, since an island can be connected to more than one Y-bridge, you would have to perform that algorithm iteratively, i.e. update the odd/even degree of vertices as you notionally add each Y-bridge.

X-bridges have three modes to consider. With enough X-bridges it’s pretty much a sure thing that some choices will partition the total graph.

Penta-bridges, of which there is one in actual Venice, are even more pathological.

Which is why I suggested in post #10 two other plausible interpretations of multi-legged bridges that avoid this whole decision space.

But I like this complicated decision space!

And the reason I suspect that the Y-bridge problem is NP-complete is because it looks an awful lot like the Boolean satisfiability problem. It’s not exactly the same, since the bridges have three states, not just two, and I’m not sure that the islands can give us the equivalent of all of the Boolean operations, but it’s at least enough to hang a suspicion on.