1
$\begingroup$

first post on this amazing community, always been a lurker, so I'm sry if my formatting sucks. I'm having a really hard time trying to solve this problem:

Given m graphs each composed of the same n vertexes, find all the pairs of equal graphs(not isomorphic).

OBLIGATION: it is possible to elaborate an algorith that does better than checking every pair of graphs.

This algorithm has to be written in C, so it must be pretty "raw". My initial idea is to create an array of Graps and for each graph I store an array containing the Degrees of my vertex, if two graphs have different degree's array then I reject the pair of graph. This method kinda creams off some of the pair but for the worst case it's bad, because if I have m/m equal graphs I'll have to check every pair anyways.

I have no clue on how to solve this problem, any suggestion is highly appreciated.

$\endgroup$
  • 2
    $\begingroup$ Hint: If you sort a list of numbers, what do you notice about the positions of equal numbers? $\endgroup$ – j_random_hacker May 21 '18 at 16:07
  • $\begingroup$ Mhh they are in consecutive positions? $\endgroup$ – Bjerg466 May 21 '18 at 16:14
  • $\begingroup$ What if in my list I have all equal numbers? Shouldn't i check every pair of numbers? $\endgroup$ – Bjerg466 May 21 '18 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.