2
$\begingroup$

These two poker hands are graph isomorphic via a trivial suit-shifting function f:

G = Ah Kc Qd Js Th

H = Ac Kd Qs Jh Tc

V(H) = f(V(G)) where f shifts the suits

Question: how do I represent these hands as graphs such that I can test for isomophism algorithmically? I assume the ranks and suits will have to form a bipartite graph, but I'm not sure how the different cards within the hand should be modeled as nodes.

===EDIT - clarifying the isomorphism===

I would like for the following two hands not to be isomorphic.

G = Ah Kc Qd Js Th

H = Ah Kc Qd Js Tc

Is there any way to restrict the model such that the first case above would be isomorphic but this second case wouldn't?

Put another way, is there any way to constrain the isomorphism tests so that they only allow for suit shifting and not rank shifting functions?

1 Answers 1

2

You should get a complete bipartite graph $G$ where $V(G) = V_1 \cup V_2$ where $V_1 = \left\{ 2,3,\ldots,10,J,Q,K,A \right\}$ and $V_2 = \left\{ Club, Heart, Diamond, Spade \right\}$. Thus a hand of 5 cards can be represented as $E' \subset E(G) s.t. |E'|=5$. Thus if you can find an isomorphism between two hands, $E_1$ and $E_2$, in the graphs $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ the two hands will be the same.

  • 0
    @Nicolas Villanueva: Apologies, since I'm still learning graph theory, but does your second sentence mean that the edge sets for G1 and G2, respectively, would be subsets of E(G) and that there would be 5 edges per edge set? Would E(G) be a full set of edges between V1 and V2?2011-05-03
  • 0
    @Nicolas Villanueva: sorry, one more question. Wouldn't your specification above call the following two hands isomorphic? AdKcQhJsTd and AdKcQhKsTc. Strictly speaking, the first hand has an Ace and Ten of the same suit, whereas the second hand has a King and ten of the same suit.2011-05-03
  • 0
    @MikeRand You are correct in your first assumption that there would be 5 edges per edge set, and that $E(G)$ would be the full set of edges since $G$ was complete bipartite. And my construction would not consider those two hands isomorphic since in the first hand the degree of the King vertex is only 1 while in the other hand it is of degree 2.2011-05-03
  • 0
    @Nicolas Villanueva: Apologies, I meant the following two hands would be isomorphic: AdKcQhJsTd and AdKcQhJsTc. I'm guessing the same logic applies: the degree of c would be 1 vs. 2.2011-05-03
  • 0
    @MikeRand Yes they would be Isomorphic, simply take the mapping f which swaps the vertices (K with A) and (D with C) and you go from the first hand to the second.2011-05-03
  • 0
    @Nicolas Villanueva: Ah, ok. Is there any way to model the hand so that they wouldn't be isomorphic?2011-05-03
  • 0
    @MikeRand Wouldn't that defeat the purpose? You want those two hand to be the same, correct?2011-05-03
  • 0
    @Nicolas Villanueva: No, I only want f(x) where x is a suit, not a rank. Poker hands are only really suit isomorphic, not rank isomorphic, even if the second example appears "equivalent". For example, the following two hands are "isomorphic" by your definition: AcKcQcJcTc and AcKcQcJc9c, with f(T) = 9, but they are not equivalent poker ranks.2011-05-03