2
$\begingroup$

Given a directed graph $G$, a node $n \in G$, is it possible (besides bruteforcing for all possible solutions) to know if there exists a path starting from the node $n$ and such that we visit each node of the graph an odd number of times?

There are no other constraints except the starting point and the fact that I have to visit all nodes of the graph respecting the previous condition.

EDIT I'll make an example. Let's consider the graph in this picture: sorry for the awful drawing and assuming I want to start with the node 'a', there is no way to visit the graph passing through each node exactly 1 time (the only path is "a, c, a, b" passing through 'a' 2 times). If the starting node is 'c', instead, it's possible to do "c, a, b" and that satisfies the conditions.

Now obviously the graph isn't fully connected, but also changing the starting point can make things possible.

EDIT 2 I now realize the term "path" could be misleading. I just need to pass through each node an odd number of times.

$\endgroup$
3
$\begingroup$

I might be very wrongly interpreting your question, but it appears to me you are asking if it is possible to determine if a graph is connected without brute-force methods. If this is not your question, my apologies. If it is your question, however, please continue reading.

To determine the connectedness (connectivity?) of a graph, you should first construct an adjacency matrix $A$. Then find a new matrix $M$ which is the sum of the integer powers of $A$ up to and including the number of largest possible path length (if you know it) or simply the number of nodes/vertices $n$: $$ M = \sum\limits_{i=1}^{n} A^i = A + A^2 + A^3 + \cdots + A^n$$ If the matrix $M$ contains any entries that are $0$'s, the graph is not connected and therefore not every vertex has a path to every other vertex. Equivalently, if all the entries of $M$ are non-zero, then the original graph is connected.

Based on your profile name, I can guess you're a fan of computational efficiency. There are ways to compute larger powers of A (a.k.a. very large number of vertices) by keeping track of the power of A with an exponent that is a power of 2. Examples: $$A^3=A^2A \\ A^6=A^4A^2\\A^{27}=A^{16}A^8A^2A^1$$ I recommend looking into the binary representation of your original exponent to find the powers of the corresponding "powers of 2" adjacency matrices. Then add them all up and see if the resulting matrix contains any zeros! If not, it is fully connected.

EDIT: Even though the binary-method of large powers is not guaranteed to give the most efficient exponentiation chain, it is certainly straightforward and easier to code (for me at least) than a brute-force method to find the most efficient exponentiation chain. See Project Euler Problem 122 and the Wiki page on Addition-chain Exponentiation for more on this. I recommend reading up on such methods if your graphs have a tremendously huge number of vertices or else the time you spend coding will be longer than the time saved by not using the binary-method explained above.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I still don't know if that answers my question, I made an edit to my original answer with an example of what I mean (hopefully claryfing things a bit). My graphs always have less than 50 vertices anyway, so I could really well code a brute force but this is more of a curiosity of mine. $\endgroup$ – The Coding Monk Jan 16 '14 at 2:52

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.