Treat Directed Graph as Undirected Graph?

237 Views Asked by At

Suppose there is a directed graph of which every two nodes have connections to each other but with DIFFERENT WEIGHTS. In this case, this is a strongly connected digraph (cycle) but not necessarily symmetric or balance. However, it also looks like a undirected graph since the connections between every two nodes are bidirectional (but with different weights).

Actually I think those theorems or properties that apply to undirected graph CANNOT apply to this kind of digraph as discussed above. Am I right?

For example, does the following theorem apply to the directed graph mentioned above?

For a connected graph $G$ that is undirected, we have: \begin{equation} \min_{x \ne 0, ~ > 1^Tx=0}\frac{x^TLx}{||x||^2}=\lambda_2(L) \end{equation} wherer $L$ is the Laplacian matrix of graph $G$ and $\lambda_2$ is the Fiedler eigenvalue of $L$, i.e., the second smallest nonzero eigenvalue.

1

There are 1 best solutions below

1
On BEST ANSWER

No, such theorems will not generalize to this kind of graph as a rule. Of course, some results might turn out to apply more generally, but you have to verify this.

In your example, if $L$ is not symmetric, the quadratic form $x^T L x$ is still the quadratic form corresponding to some symmetric matrix: it is equal to $x^T \left(\frac{L + L^T}{2}\right)x$. So we have \begin{equation} \min_{x \ne 0, 1^Tx=0}\frac{x^TLx}{||x||^2} = \min_{x \ne 0, 1^Tx=0}\frac{x^T\left(\frac{L + L^T}{2}\right)x}{||x||^2} = \lambda_2\left(\frac{L + L^T}{2}\right)\end{equation} and you will basically never have $\lambda_2\left(\frac{L + L^T}{2}\right) = \lambda_2(L)$ except by coincidence. So the theorem is not true, and just about every $2$-node weighted digraph you try will give you a $2 \times 2$ counterexample.