1
$\begingroup$

Let $G$ be a connected graph with $V$ vertices and let say I have an adjacency matrix of order $N$, how can I make sum of each column even?

Like I have a graph with $4$ vertices and $4$ edges as

$\begin{bmatrix}0 & 1 & 0 &0 \\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}$

And I want to convert it like this,

$\begin{bmatrix}0 & 0 & 0 &0 \\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 \end{bmatrix}$

For reference, if $i^{th}$ element of the $j^{th}$ row is $1$ then the edge is directed from $j$ to $i$.

You can reverse any edge between two vertices such that the graph remains connected. And the adjacency matrix's indexing starts from 1 rather than from 0.

$\endgroup$
  • 3
    $\begingroup$ Depends on what operations you allow yourself to use. $\endgroup$ – Michal Adamaszek Dec 13 '18 at 6:54
  • $\begingroup$ I've added the operation which you can use in the last sentence. $\endgroup$ – Sahil Silare Dec 21 '18 at 7:02
1
$\begingroup$

As mentioned in the comments, this depends on what operations you allow, because you are clearly allowing your underlying graph to change --- the graph after your transformation isn't isomorphic to the first graph.

For your first matrix, you have the following graph:

First graph

For your second matrix, you have the following:

Second graph

Taken as directed graphs, these are not isomorphic (however, if you relax them to merely undirected, they are). As such, it's difficult to determine what operations you're allowing as legal transformations.

$\endgroup$
  • $\begingroup$ I've added the allowed operation in the last sentence of the question. Can you elaborate your answer? $\endgroup$ – Sahil Silare Dec 21 '18 at 7:03
  • $\begingroup$ @SahilSilare with those rules, you still might not be able to do so. Consider the graph formed by two nodes with one edge like so: $\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$. No matter what, you can't get an even number of $1$'s in a single column/row. $\endgroup$ – apnorton Dec 22 '18 at 17:42
  • $\begingroup$ I'm not saying even number of ones, I'm saying to make the the sum of each column even, it can be either $0$ or $2$ or any even number. $\endgroup$ – Sahil Silare Dec 22 '18 at 17:48
  • $\begingroup$ @SahilSilare "even number of 1s" is equivalent to "even sum of values" since every value is $0$ or $1$. $\endgroup$ – apnorton Dec 22 '18 at 17:54
  • $\begingroup$ Can't you just reverse the direction between 2 odd column indexes? $\endgroup$ – Sahil Silare Dec 22 '18 at 17:55

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.