CODEWITHSUNDEEP
algorithmmathgraph
George
George

Reputation: 35

find a common subgraph

I am trying to find to get the common subgraph given two graphs. If I have 2 graphs G1=(v1,e1) and G2=(v2,e2) i must find the common subgraf G=(V,E) such as to any another common subgraph of G1 and G2 mustn't contain more then cardinal of E arris.

Given that Graph 1 is

A - B

A - C

B - D

D - E

Graph 2 is

A - B

A - E

B - D

Than the algorithm should return

A - B

B - D

Can you help me with an algorithm which tells me what steps to attend? Thanks!

Upvotes: 1

Views: 365

Answers (1)

amit
amit

Reputation: 178451

You are not describing your problem formally, but from your example1, it seems you are looking for a largest common subset of edges.

To achieve it - you simply need the intersection of E1 and E2.

Proof:

(->) Assume (a,b) is in E1 [intersection] E2. By definition of set intersection - it is common to both E1 and E2 - and thus to G1 and G2 as well.

(<-) Assume (a,b) is common to G1 and G2 - then (a,b) is in E1 and (a,b) is in E2 - from definition of intersection, (a,b) is in E1 [intersection] E2

(1) I conclude that because (A,C) is not "common", and yet (A,B) is in the subgraph - meaning this is not a restriction of finding a subset of vertices that can create the desired subgraph (because then A should have been excluded from the result).

Upvotes: 3

Related Questions