Results 1 to 3 of 3

Thread: graph

  1. January 19th 2011, 01:21 PM #1
    cantona
    cantona is offline
    Newbie
    Joined
    Dec 2010
    Posts
    15

    graph

    Hi!

    I have d-regular bipartite graph with two sets, each link has one edge in one set and another edge in second set. Graph has preference relations.

    How can I prove that graph contains stable matching cardinality at least d?


    Thank you in advance!
    Follow Math Help Forum on Facebook and Google+
  2. January 19th 2011, 06:19 PM #2
    snowtea
    snowtea is offline
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    The Gale-Shapley algorithm is a well known solution to this problem. You should look it up
    Follow Math Help Forum on Facebook and Google+
  3. January 20th 2011, 07:18 AM #3
    cantona
    cantona is offline
    Newbie
    Joined
    Dec 2010
    Posts
    15
    On cases I know how to do this, but how can I prove this in general?
    Follow Math Help Forum on Facebook and Google+
« English to Proposition Statements | order prpoperties »

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. Graph the equation of the translated graph in general form?
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: August 5th 2011, 01:30 PM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Graph Theory: Relationship between maximum degree of a graph and maximal matching
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Potential Energy Graph for a Reaction (can someone explain the graph please?)
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: February 15th 2009, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum