Edited by Caidoz, Mark Davis, Frostmaker84, Flickety and 2 othersPin ItArticle EditDiscussThere are many occasions in life where you need to match up the elements of two sets. On most occasions this is a problem you'll probably tackle without really considering that you're doing it. However, should an occasion ever arise where there are too many options to solve it in your head, or you just want to ensure you match them all up correctly, this article should help you to achieve just that. Steps1Draw two lines of dots. You need a line for each set, with one dot for each option within the set.
2Label these dots to prevent confusion later.
3Join up all of the possible matches. In this example the sets match up in the following way:A: 1, 2 or 4B: 1C: 2 or 3D: 4 or 5E: 3.
4Choose an initial matching by pairing up the sets along these lines. Don't bother trying to find the best way to pair them up unless it's really obvious. This is just to provide something to work with in the next steps. If you do manage to match up all the pairs, you're done.
5Create a path. Make the path around your graph, going from an unmatched dot on the left side, to an unmatched dot on the right side, considering all "paired" (blue) lines to "travel" from right to left while all "unpaired" (red) lines travel from left to right, and switching the "direction" or colour of each line you go down. This will give a different matching with one more pair than the original.
6Repeat. Repeat step 5 until a complete matching has been achieved or there is no suitable path, then remove all unused (red) lines. What is left is your maximal matching.
Related wikiHowsHow to Carry out the Simplex AlgorithmHow to Use Dijkstra's AlgorithmHow to Use the Nearest Neighbour AlgorithmHow to Use the Hungarian Algorithm
This is so freaking awesome you gonna love it
Article Info Featured Article
Categories: Featured Articles | Mathematics
Was this article accurate?
YesNo
2Label these dots to prevent confusion later.3Join up all of the possible matches. In this example the sets match up in the following way:A: 1, 2 or 4B: 1C: 2 or 3D: 4 or 5E: 3.4Choose an initial matching by pairing up the sets along these lines. Don't bother trying to find the best way to pair them up unless it's really obvious. This is just to provide something to work with in the next steps. If you do manage to match up all the pairs, you're done.5Create a path. Make the path around your graph, going from an unmatched dot on the left side, to an unmatched dot on the right side, considering all "paired" (blue) lines to "travel" from right to left while all "unpaired" (red) lines travel from left to right, and switching the "direction" or colour of each line you go down. This will give a different matching with one more pair than the original.6Repeat. Repeat step 5 until a complete matching has been achieved or there is no suitable path, then remove all unused (red) lines. What is left is your maximal matching.Related wikiHowsHow to Carry out the Simplex AlgorithmHow to Use Dijkstra's AlgorithmHow to Use the Nearest Neighbour AlgorithmHow to Use the Hungarian Algorithm
This is so freaking awesome you gonna love it
Article Info Featured Article
Categories: Featured Articles | Mathematics
Was this article accurate?
YesNo
No comments:
Post a Comment