10. Another application of graphs is a kidney exchange program: Suppose that an individual is willing to Jonate a kidney

[answerhappygod]

10 Another Application Of Graphs Is A Kidney Exchange Program Suppose That An Individual Is Willing To Jonate A Kidney 1 (51.51 KiB) Viewed 41 times

10. Another application of graphs is a kidney exchange program: Suppose that an individual is willing to Jonate a kidney to a relative or friend who needs a kidney transplant. In the case that they are not a match with their relative or friend, they are willing to donate a kidney to someone else needing a transplant. The goal then is given a group of potential donors and recipients along with the information about all compatible/incompatible donor-recipient pairs, determine the maximum number of kidney exchanges (transplants) that can be carried out. Consider the following situation: There are 4 people who need a kidney transplant: Ry, Rz, Ry, and Rs. The 4 potential donors are D , D2, D3, and D. The following lists show which donors are a match with each recipient who is in need of a transplant. R: D₂, D₂ R2: D2.D R3: D.D Re: D₂, D₂ a) Construct a graph that conveys the information the above lists. Be sure to label the vertices and describe the relationship that the edges represent. b) Find a subgraph of your graph in (a) that represents the donor-recipient matches resulting in the maximum number of kidney transplants. c) (i) The graph that describes the possible recipient donor matches will always be what type of graph? (ii) The subgraph that represents the recipient-donor matches with the maximum number of kidney transplan will always be what type of graph?