Zusammenfassung
Es wird ein Algorithmus zur Ermittlung eines maximalen Matching angegeben, dessen Vorteil darin besteht, daß er auf beliebige auch nichtpaare Graphen angewendet werden kann und ohne Schwierigkeiten auf einem Computer ausgeführt werden kann. Ein entsprechendes Programm wurde an verschiedenen Graphen getestet.
Summary
There are two advantages of the algorithm given in the paper: (I) It applies to bipartite as well as to nonbipartite graphs and (II) it is easy to implement it on a computer. A computer program based on the algorithm has been tested using various graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Literatur
Berge, C.: The Theory of Graphs. London: J. Wiley. 1962.
Busacker, R. G., undTh. L. Saaty: Endliche Graphen und Netzwerke. München: Oldenbourg. 1968.
Edmonds, J.: Paths, trees and flowers. Canad. J.Math.17, 449–467 (1960).
Egerváry, E.: On Combinatorial Properties of Matrices. Office Naval Res. Logist Project Rept., Dpt. of Math., Princeton University. 1953.
Ford, L. R., andFulkerson D. R.: Maximal flow through a network. Canad. J. Math9, 210–218 (1956).
Harary, F.: Graph Theory. London: Addison Wesley. 1969.
Kuhn, H. W.: The Hungarian method for solving the assignment problem. Naval. Res. Logist. Quart.3, 253–258 (1956).
Liu, C. L.: Introduction to Combinatorial Mathematics. New York: McGraw-Hill. 1968.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dörfler, W., Mühlbacher, J. Bestimmung eines maximalen Matching in beliebigen Graphen. Computing 9, 251–257 (1972). https://doi.org/10.1007/BF02246734
Received:
Issue date:
DOI: https://doi.org/10.1007/BF02246734