Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

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.

share|improve this answer
    
@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? –  MikeRand May 3 '11 at 1:01
    
@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. –  MikeRand May 3 '11 at 1:50
    
@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. –  Nicolas Villanueva May 3 '11 at 5:55
    
@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. –  MikeRand May 3 '11 at 8:03
    
@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. –  Nicolas Villanueva May 3 '11 at 8:57
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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