際際滷

際際滷Share a Scribd company logo

An approach to compare graphs using vertex degrees - graph isomorphism

Download as PPTX, PDF
Sandeep Kunkunuru
Sandeep Kunkunuru

A hypothetical approach with an example. No proof is provided. Approach tries to use a seemingly mandatory rule for two graphs to be isomorphic, it isnt proved or argued that the rule is sufficient by itself for isomorphism, that's essentially hoped for.

1 of 9
An Approach to Compare Graphs - Using vertex degrees for Graph Isomorphism Problem -
Problem Statement Can two graphs, constructed independent of each other, be isomorphic. Restating the same - Can one graph be redrawn as the other.
Problem - Illustrative Example 1. G1 and G2 are isomorphic 2. G3 - is not isomorphic to G1 and G2 (Typo in the pic)
Approach - Key Thoughts and Steps THOUGHTS: 1. There may be nodes within a graph that can be substituted for each other without changing the graph structure. That is the labels of two identical nodes can be exchanged to produce an isomorphic graph. 2. Two nodes can be called identical or substitutable if their BFS patterns are the same. BFS pattern of a node can be defined as sorted sequence of the number of unmarked nodes that can be accessed in each hop from the current node. a. For example in G1 : since A BDFC AE, AD, AI DH, FG therefore A has a BFS pattern of 4-1010- 11 since 4 nodes can be accessed from A in 1 hop, 2 more in the second hop and 2 more in the third hop. b. The pattern can be represented as a number ex: here the number is 4001111. (At each hop we need to sort the accessible nodes i.e. 101 is sorted) 3. identical nodes can be grouped together into a corresponding pattern Bag. 4. A set of Bags of BFS patterns uniquely identifies the graph completely. 5. If two graphs can be defined in terms of the same set of bags of same patterns then they are isomorphic. i.e. if we derive the bags of same patterns. STEPS: 1. Construct BFS patterns for each node in each of the two graphs. 2. Group nodes in each graph into their corresponding pattern Bags. Each Bag is uniquely identified by the single BFS pattern of its components.Sort the bags of each graph by their pattern number 3. compare the two sorted arrays.
Solution - Illustrative Example 1. G1 and G2 are isomorphic 2. G3 - is not isomorphic to G1 and G2 (Typo in the pic)
Solution - Illustrative Example In the previous example G1 o BFS patterns are as follows A - 4-0011-11- 4001111 (A BDFC AD, AE, AI DH, FG) similarly B - 212011001 (B AD CF, E A, AI, DH FG, ABE, EG) C - 1301111 D - 301211 E - 212012 F - 213001101 G - 2111111, 2111102 (G I, H F, E A, D C, B or BC ). The tie between these options can be broken by identifying such situations ahead picking one by.? One Refined alternative approach is in next slide. H - 21112001 I - 21113 o Bags are G2 - Bags are - G3 - Bags are - Given above G1, G2 are isomorphic G3 is not isomorphic to G1 and G2
Alternative working approach Approach is same as before except that we use degrees at each node instead of number of accessible unmarked nodes. Also at each level we still sort the degrees.
Solution - Illustrative Example In the previous example G1 o BFS degree patterns are as follows A - 4-1222-22 i.e. 4122222 (A BDFC AD, AE, AI, A DH, FG) B - 22212222 (B AD CF, AE A, AI, DH FG, EG) C - 1322322 D - 322323 E - 212223 F - 22312223 G - 22233 (G I, H FG, EG AI, DH CBD, ABE).We don't have a tie this time H - 222232223 I - 2222223122 o Bags are G2 - Bags are - G3 - Bags are - Given above G1, G2 are isomorphic G3 is not isomorphic to G1 and G2
Solution - Complexity 1. Step1 - O(n^2) - There could be possibly be better algorithms that can be devised to generate BFS patterns faster. 2. Step2 - O(nlogn) - This is a sorting problem for the BFS patterns identified by numbers. 3. Step3 - O(m) - Where m is the number of bags The complexity of this solution is therefore O(n^2). Which can be optimised further by finding an optimal algorithm for quickly construction BFS patterns of all nodes.

More Related Content

An approach to compare graphs using vertex degrees - graph isomorphism

  • 1. An Approach to Compare Graphs - Using vertex degrees for Graph Isomorphism Problem -
  • 2. Problem Statement Can two graphs, constructed independent of each other, be isomorphic. Restating the same - Can one graph be redrawn as the other.
  • 3. Problem - Illustrative Example 1. G1 and G2 are isomorphic 2. G3 - is not isomorphic to G1 and G2 (Typo in the pic)
  • 4. Approach - Key Thoughts and Steps THOUGHTS: 1. There may be nodes within a graph that can be substituted for each other without changing the graph structure. That is the labels of two identical nodes can be exchanged to produce an isomorphic graph. 2. Two nodes can be called identical or substitutable if their BFS patterns are the same. BFS pattern of a node can be defined as sorted sequence of the number of unmarked nodes that can be accessed in each hop from the current node. a. For example in G1 : since A BDFC AE, AD, AI DH, FG therefore A has a BFS pattern of 4-1010- 11 since 4 nodes can be accessed from A in 1 hop, 2 more in the second hop and 2 more in the third hop. b. The pattern can be represented as a number ex: here the number is 4001111. (At each hop we need to sort the accessible nodes i.e. 101 is sorted) 3. identical nodes can be grouped together into a corresponding pattern Bag. 4. A set of Bags of BFS patterns uniquely identifies the graph completely. 5. If two graphs can be defined in terms of the same set of bags of same patterns then they are isomorphic. i.e. if we derive the bags of same patterns. STEPS: 1. Construct BFS patterns for each node in each of the two graphs. 2. Group nodes in each graph into their corresponding pattern Bags. Each Bag is uniquely identified by the single BFS pattern of its components.Sort the bags of each graph by their pattern number 3. compare the two sorted arrays.
  • 5. Solution - Illustrative Example 1. G1 and G2 are isomorphic 2. G3 - is not isomorphic to G1 and G2 (Typo in the pic)
  • 6. Solution - Illustrative Example In the previous example G1 o BFS patterns are as follows A - 4-0011-11- 4001111 (A BDFC AD, AE, AI DH, FG) similarly B - 212011001 (B AD CF, E A, AI, DH FG, ABE, EG) C - 1301111 D - 301211 E - 212012 F - 213001101 G - 2111111, 2111102 (G I, H F, E A, D C, B or BC ). The tie between these options can be broken by identifying such situations ahead picking one by.? One Refined alternative approach is in next slide. H - 21112001 I - 21113 o Bags are G2 - Bags are - G3 - Bags are - Given above G1, G2 are isomorphic G3 is not isomorphic to G1 and G2
  • 7. Alternative working approach Approach is same as before except that we use degrees at each node instead of number of accessible unmarked nodes. Also at each level we still sort the degrees.
  • 8. Solution - Illustrative Example In the previous example G1 o BFS degree patterns are as follows A - 4-1222-22 i.e. 4122222 (A BDFC AD, AE, AI, A DH, FG) B - 22212222 (B AD CF, AE A, AI, DH FG, EG) C - 1322322 D - 322323 E - 212223 F - 22312223 G - 22233 (G I, H FG, EG AI, DH CBD, ABE).We don't have a tie this time H - 222232223 I - 2222223122 o Bags are G2 - Bags are - G3 - Bags are - Given above G1, G2 are isomorphic G3 is not isomorphic to G1 and G2
  • 9. Solution - Complexity 1. Step1 - O(n^2) - There could be possibly be better algorithms that can be devised to generate BFS patterns faster. 2. Step2 - O(nlogn) - This is a sorting problem for the BFS patterns identified by numbers. 3. Step3 - O(m) - Where m is the number of bags The complexity of this solution is therefore O(n^2). Which can be optimised further by finding an optimal algorithm for quickly construction BFS patterns of all nodes.