Matching

Matching

Matching

En matemática discreta y en particular en la teoría de grafos, un matching o conjunto independiente de aristas (también llamado emparejamiento o apareamiento) en un grafo es un conjunto de aristas independientes, es decir, sin vértices en común.

Contenido

Definición

Dado un grafo G = (V,E) \, un matching M en G es un conjunto de aristas no adyacentes entre sí.

Decimos que un vértice está matched (acoplado, apareado o saturado) si es incidente con una arista en el matching. En otro caso, el vértice está unmatched (libre).

Un matching máximo es un matching que contiene el número máximo posible de aristas. Pueden haber muchos matchings máximos. El número de matching de un grafo es el tamaño del matching máximo.

Un matching maximal es un matching M de un grafo G con la propiedad de que si alguna arista que no pertenece a M es añadido a M, no será ya un matching. Nótese que todos los matching máximos deben ser maximales, pero no todos los matching maximales deben de ser máximos.

Un matching perfecto es un matching que cubre todos los vértices del grafo. Ésto es, cada vértice está saturado bajo el matching. Cada matching perfecto es máximo y maximal.

Dado un matching M

  • una trayectoria M-alternante es una trayectoria en la cual sus aristas alternativamente pertenecen y no pertenecen al matching.
  • una trayectoria M-aumentante es una trayectoria M-alternante que comienza y termina en un vértice libre (unmatched).

Nótese que un matching es máximo si y sólo si no contiene ninguna trayectoria M-aumentante.

Matchings en grafos bipartitos

Los problemas de matching tienen relación muchas veces con grafos bipartitos. Encontrar un matching máximo bipartito (a menudo llamado cardinalidad máxima de un grafo bipartito) en un grafo bipartito G=(V=(X,Y),E) \, es quizás el problema más simple. El algoritmo de los caminos aumentantes lo encuentra por búsqueda de caminos aumentantes por cada x \in X a Y\, y añadiéndolo al matching si existe. Como cada camino puede ser encontrado en tiempo O(E)\,, el costo de tiempo es O(V E)\,. Todas las aristas con flujo de X\, a Y\, constituyen un matching máximo. Una mejora sobre esto es el algoritmo de Hopcroft-Karp, de costo de tiempo O(\sqrt{V} E)\,.

En un grafo bipartito ponderado, cada arista tiene asociado un valor. Un matching máximo bipartito ponderado está definido como un matching perfecto donde la suma de los valores de sus arcos en el matching tiene un valor maximal. Si el grafo no es completamente bipartito, los arcos ausentes son introducidos con valor cero. Encontrar tal matching es conocido como problema del asignamiento. Para resolverlo se usa la búsqueda del camino mínimo modificado con el algoritmo del camino aumentante. Si usamos el algoritmo de Bellman-Ford, con costo de tiempo O(V^2 E)\,. El más especializado es el algoritmo Húngaro que resuelve el problema de asignación con costo de tiempo O(V^3)\,.

Propiedades

  • [1] Para un grafo G con n vértices con un vértice aislado el número de matching + número de aristas de covering = n
  • Un grafo con n vértices y un matching perfecto tiene un número de matching igual a n/2

Véase también

Referencias

  1. Gallai, Tibor. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.3: Maximum bipartite matching, pp.664–669.
  • West, Douglas Brent (1999). «3», Introduction to Graph Theory, 2nd edition edición, Prentice Hall. ISBN 0-13-014400-2.
Obtenido de "Matching"

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Matching — may refer to: Matching (graph theory), in graph theory, a set of edges without common vertices Matching (statistics), a technique for reducing bias when analyzing data from observational studies String matching, in computer science Matchmaking,… …   Wikipedia

  • Matching — (engl. dazu passend oder: der Vorgang des Passend Machens ) steht für: Matching (Arbeitsvermittlung), Abgleich bzw. Zuordnung von Arbeitsplatzanforderungen und Kompetenzen Matching (Partnervermittlung), eine Methode der Online Partnervermittlung… …   Deutsch Wikipedia

  • matching — adj. 1. having identical or closely similar appearance or properties; as, a pair of matching candlesticks. Syn: duplicate, twin(prenominal), twinned. [WordNet 1.5] 2. Harmonious and pleasing in appearance when used together; as, a matching skirt… …   The Collaborative International Dictionary of English

  • matching — matching; non·matching; …   English syllables

  • matching — index agreed (harmonized), analogous, coequal, commensurable, commensurate, comparable (equivalent) …   Law dictionary

  • Matching —   Matching is the concept of recognising cost expirations (expense) in the same accounting period when the related revenues are recognised …   International financial encyclopaedia

  • matching — [adj] corresponding, equal analogous, comparable, coordinating, double, duplicate, equivalent, identical, like, paired, parallel, same, twin; concept 566 Ant. different, uncorrespondent, unequal …   New thesaurus

  • matching — See crossing and accruals. Dresdner Kleinwort Wasserstein financial glossary The process for comparing the trade or settlement details provided by counterparties to ensure that they agree with respect to the terms of the transaction. Euroclear… …   Financial and business terms

  • matching — 1. adjective /ˈmætʃɪŋ/ The same as another; sharing the same design. A matching set of furniture 2. noun /ˈmætʃɪŋ/ A set of independent edges in a given graph, i.e. a set of edges which do not intersect: so called because pairs of vertices are… …   Wiktionary

  • matching — vienodinimas statusas T sritis biomedicinos mokslai apibrėžtis Tiriamosios ir kontrolinės grupių vienodinimas atsižvelgiant į gretutinius požymius. Yra kelios vienodinimo rūšys: 1) porinimas (pair matching) – procesas, kai kiekvienam tiriamosios… …   Lithuanian dictionary (lietuvių žodynas)

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”