UKH

If I ask the question "is it possible to tour Skye and the Outer Hebrides starting and finishing on the mainland using each ferry only once?"

Am I in fact asking "can I draw a graph where each island with a ferry service and the mainland is a vertex, each ferry route an edge and every vertex has an even degree"?

In reply to DaveHK:

I plotted a route that got to most, but also included Arran, Mull and other inner Hebrides. Some of the small islands only have one ferry.

Arran to Islay is good, you can go on and off Arran with different ferries, hopping the mainland.

Do you want the actual mathematical answer or just the best route for doing the most islands with fewest ferries.

In reply to DaveHK:

Here it is:

Skye, Harris, N Uist, Barra, Mull, Oba

Then you drive down and get the ferry to Islay. As you now can't reverse that route, you retire and live on Islay (occasionally swimming across to Jura to sample their excellent whisky when you momentarily tire of by the Islay selection).

Don't take the ferry to Soronsay, lovely but if you get stuck there its beer only forever.

If this is a holiday, rather than some legally binding contract with Calmac, then I recommend Finals cave (Staffa) from Mull and also Iona. Also Arran. Soronsay (as above, great by boat).

Jura is aweesome, there is a beach to the north with a walkie talkie on a table. You use it to order tea and cake and a lady comes down the road with it. Magical.

In reply to Philip:

There are ferries to Port Ellen and Port Askaig on Islay, although admittedly they start at the same place. If you were on the bike (in summer), you could come in via the Tayvallich to Craighouse ferry (mainland to Jura), then back out via Feolin and one of the Islay ferries. I've been looking at many of these options recently.

In reply to DaveHK:

Sorry guys, I was looking for the mathematical answer rather than suggested routes. But thanks anyway.

In reply to DaveHK:

Your question isn't well posed. E.g. "... where each island with a ferry service and the mainland is a vertex ..." What about an island with more than one ferry service?

In reply to Rob Parsons:
So change it to each island with one or more ferry service although in practical terms one would need to leave out places like Raasay with only one route onto and off the island and treat the islands linked by bridges and causeways as one entity. I think.

In reply to DaveHK:

Isn't your question a variant of this?

https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

In reply to DaveHK:


Would it count as re-using a ferry to take a return journey on it? If there are more than two islands connected to the mainland, then you'll be going to the mainland mid-trip if you really wanted to use every ferry.



What's an "even degree"? I assume it's fundamental to the question, as drawing a graph with islands & mainland as vertices and ferries as edges is trivial.

If you're looking for a logic problem, a more normal question would be e.g. find the shortest route visiting all islands, starting and finishing on the mainland.

In reply to MG:



Yes. That was what inspired it.

In reply to humptydumpty:

Except the shortest route could involve using a ferry more than once.

As I understand it a vertex has even degree if the number of edges incident to it is an even number.

In reply to humptydumpty:


Yes.

In reply to DaveHK:

In response to the original question... Yes. You're describing a Eulerian cycle.

No bike gags please.

In reply to Clinger:

Thanks, that was the confirmation I was looking for however poorly I phrased it!

In reply to DaveHK:

I thought you could have two nodes that have an odd degree - the start and the finish. That is what it says on the Wikipedia Konigsberg bridges link, and it makes sense.

In reply to mbh:

You can but only if you have different start and finish points which is an Eulerian path. I'd specified starting and finishing on the mainland which would be an Eulerian Circuit as start and finish are the same and for this there must be no nodes with odd degree.

In reply to DaveHK:

Aha - so you did!