Menentukan Penjodohan Stabil pada Garaf Bipartisi Berbobot Menggunakan Algoritma Gale-Shapley

Abstract

Abstract – Stable matching is one of the topics in graph theory, as an application of weighted bipartite graph.On completion of the process of stable matching is used an algorithm is called Gale-Shapley algorithm. To find the stable matching in research, to analyzed stable matching in any weighted bipartite graph  with  and , any weighted complete bipartite graph  with  and , as well as also example of the application of stable matching using Gale-Shapley algorithm. Research purposes to determine stable matching in weighted bipartite graph using Gale-Shapley algoritm. The results of this research is using step by step Gale-Shapley algoritm untill get stable matching. Stable matching is only obtained on arbitrary any weighted bipartite graph  with  and any weighted complete bipartite graph  with . In any weighted bipartite graph  with  and any weighted complete bipartite graph  with , obtained maximum matching. Stable matching which has  element of a set of large, can be solved with a program Python 3.5.1.

Keywords – Matching, Graph, Gale-Shapley Algorithm