1
$\begingroup$

Two undirected graphs $G$ and $H$ on the vertices $1,2,\ldots,n$ are disjoint if the intersection of their edge sets is empty. Assume both $G$ and $H$ are represented by adjacency matrices.

Describe an efficient algorithm that decides if $G$ and $H$ are disjoint. What is the complexity of your algorithm? Justify the correctness of your algorithm and your complexity claim.

What I am thinking is just picking an arbitrary vertex on either graph like $G$ and checking if we can reach a vertex from the other graph $H$ by running some simple traversal like DFS. Is there a better way? I am thinking what if we go through the adjacency matrix of one graph and check if any edge connects a vertex from one graph to the other.

$\endgroup$
5
  • 1
    $\begingroup$ It seems to me that you have not really understood what it means that graphs are disjoints. Please re-read the definition. It is a good idea to use the adjacency matrix, but what does it mean that a edge connects a vertex from one graph to the other? $\endgroup$
    – Nathaniel
    Apr 22, 2021 at 23:17
  • $\begingroup$ @Nathaniel isn't exactly what you said an edge connecting one vertex from one graph to the other? I am confused $\endgroup$
    – Benny
    Apr 22, 2021 at 23:26
  • $\begingroup$ Graphs may be edge disjoint and vertex disjoint, and your definition describes edge disjoint ones. So, they might have common vertices and your idea with DFS won't work. $\endgroup$
    – HEKTO
    Apr 23, 2021 at 3:22
  • $\begingroup$ so what is a better way? $\endgroup$
    – Benny
    Apr 23, 2021 at 3:39
  • 1
    $\begingroup$ As an example, you could have $E_G = \{\{1, 2\}, \{3, 4\}, \{5, 6\}\}$ and $E_H = \{\{2, 3\}, \{4, 5\}, \{6, 7\}\}$. This is an example of two disjoint graphs, because they have no edge in common. Is this clearer? $\endgroup$
    – Nathaniel
    Apr 23, 2021 at 6:39

1 Answer 1

1
$\begingroup$

The adjacency matrix $A_G$ of an undirected graph $G=(V,E)$ is defined as follows: $A_G$ is a $V \times V$ matrix, $A_G(v,v) = 0$ for all $v \in V$, and $A_G(u,v) = 1$ if $\{u,v\} \in E$ and $A_G(u,v) = 0$ if $\{u,v\} \notin E$.

Two graphs $G,H$ are edge-disjoint if there doesn't exist an edge $\{u,v\}$ which belongs to both of them. That is, $G,H$ are edges-disjoint if there do no exist $u,v$ such that $A_G(u,v) = A_H(u,v) = 1$.

You take it from here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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