Example 2: The Marriage Problem: Given a set of men, each of whom knows some women from a given set of women, under what conditions is it possible for all men to marry women they know? Four men each know some of four women Peter knows Mary and Ann Kevin knows Mary, Ann, Rose and Tina Brian knows Mary and Ann Fred knows Ann Is it possible for all the men to marry women they know? Graph matching ary eter ose Brian ●Tina Fred▪ Example 2: The Marriage Problem:Given a set of men, each of whom knows some women from a given set of women, under what conditions is it possible for all men to marry women they know? ▪ Four men each know some of four women ▪ Peter knows Mary and Ann ▪ Kevin knows Mary, Ann, Rose and Tina ▪ Brian knows Mary and Ann ▪ Fred knows Ann ▪ Is it possible for all the men to marry women they know? ▪ Graph Matching