5
$\begingroup$

enter image description here

Rules:
1. Start from point A reach back to point A.
2. Each path needs to be visited at least once and only once in each journey.
3. never turning off at crossroads.

to make it more understandable

path = AB, BC etc
journey = ABCDEBDACE or AECADBEDCBA

How many different journeys exist?

| improve this question | |
$\endgroup$
  • $\begingroup$ If ABCDEBDACEA is a path, is AECADBEDCBA also counted? $\endgroup$ – JMP Oct 9 '19 at 8:40
  • $\begingroup$ Can you precise what are "Path" and "Journey" in the context of this question ? $\endgroup$ – Evargalo Oct 9 '19 at 9:10
  • 1
    $\begingroup$ "Each path needs to be visited at least once and only once in each journey" - Do you mean each edge needs to be used exactly once? So are you really asking how many Eulerian circuits this graph has? $\endgroup$ – Jaap Scherphuis Oct 9 '19 at 9:20
  • $\begingroup$ Oh, so you are asking for Hamiltonian circuits? But then the title doesn't seem to fit the question anymore? $\endgroup$ – Evargalo Oct 9 '19 at 10:07
  • 2
    $\begingroup$ @Evargalo Not Hamiltonian, Eulerian. Every edge has to be used exactly once, not every vertex. But yes, the title makes no sense given that in the question "path" was used to mean an edge. $\endgroup$ – Jaap Scherphuis Oct 9 '19 at 10:09
5
$\begingroup$

Each node has 4 edges, so is visited twice. We start and end on node A, but it must be visited some time in between as well.

Let's split this up into cases depending on how many other nodes are visited before we come back to A the first time.

A node cannot be travelled back to immediately because that reuses the same edge, so between two visits to a node at least two other nodes are visited.

1. Node A is visited after 4 other nodes, i.e. $A....A....A$. There can be no repeats in the two halves (they must be at least 2 apart, so it would have to be $AX..XA$, but that repeats edge $AX$). So all four other nodes are visited in some order in the first half. There are $4!=24$ such orderings. The second half of the route is then fixed, apart from the direction. This gives $48$ such routes.

2. Node A is visited after 5 other nodes, i.e. $A.....A...A$. There must be exactly one repeat in that first section, so $AX..X.A$ or its reverse. Any more repeats or putting the repeat further apart will cause edges to be used twice. The blanks are then the other 3 nodes in any order. This means there are $4!*2=48$ choices for this section. The second half is again fixed apart from direction, so we have $96$ such routes.

3. Node A is visited after 6 other nodes, i.e. $A......A..A$. There must be exactly two repeats in that first section. The only patterns that work without repeating any edges are $AXY.X.YA$, its reverse, and $AX.YX.YA$. The blanks are then the other 2 nodes. This means there are $4!*3=72$ choices for this section. The second half is again fixed apart from direction, so we have $144$ such routes.

4. Node A is visited after 3 other nodes. This is case 2 in reverse, so also $96$ routes.

5. Node A is visited after 2 other nodes. This is case 3 in reverse, so also $144$ routes.

This gives a total of:

$48+2*96+2*144 = 528$ routes.

More explicitly, the routes are:

Using the digits $1$-$4$ to stand for the letters $B$-$E$ in any order:
1. $A1234A2413A$, $A1234A3142A$
2. $A12314A243A$, $A12314A342A$, $A21341A423A$, $A21341A324A$
3. $A123142A34A$, $A123142A43A$, $A132412A34A$, $A132412A43A$, $A132142A34A$, $A132142A43A$
4. $A243A12314A$, $A342A12314A$, $A423A21341A$, $A324A21341A$
5. $A34A123142A$, $A43A123142A$, $A34A132412A$, $A43A132412A$, $A34A132142A$, $A43A132142A$

| improve this answer | |
$\endgroup$
  • $\begingroup$ @JMP I don't think so. I count ABCDEACEBDA and ABCDEADBECA (only the second half reversed), and then times the 4! permutations of the labels BCDE. $\endgroup$ – Jaap Scherphuis Oct 9 '19 at 11:29
  • $\begingroup$ @JMP All circuits in this question have a direction. If you want undirected circuits, the final answer has to be divided by two. Note that the cases 2 and 4 are reverses of each other, as are 3 and 5. Case 1 is reverse of itself, so there are only 24 undirected circuits for that case, but I am counting them with direction here. $\endgroup$ – Jaap Scherphuis Oct 9 '19 at 11:36
0
$\begingroup$

Edit : This is an answer to the question:

How many different paths exist from A to A that go through each other point exactly once ?

However, per the comments, it seems the OP is looking for something else. I cannot figure out what exactly yet.

There are

24

paths that qualify.

Indeed,

Each path must be of the type A????A where each ? stands for either B,C,D, or E.
The number of arrangements of {B,C,D,E} into the four positions marked with ?s is 4!=24

| improve this answer | |
$\endgroup$
  • $\begingroup$ @SayedMohdAli Maybe I need more clarification. I'll comment under the question. $\endgroup$ – Evargalo Oct 9 '19 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.