000110383 001__ 110383 000110383 005__ 20220210105304.0 000110383 037__ $$aTAZ-TFG-2021-2760 000110383 041__ $$aspa 000110383 1001_ $$aUrricelqui Olcoz, Cristina 000110383 24200 $$aThe maximum matching problem in a graph 000110383 24500 $$aEl problema de matching óptimo en un grafo 000110383 260__ $$aZaragoza$$bUniversidad de Zaragoza$$c2021 000110383 506__ $$aby-nc-sa$$bCreative Commons$$c3.0$$uhttp://creativecommons.org/licenses/by-nc-sa/3.0/ 000110383 520__ $$aUn matching en un grafo G=(V,E) es un subconjunto de ejes K de manera que ningún par de ejes en K tenga vértices comunes. El problema que vamos a resolver a lo largo de este trabajo es el de encontrar un matching máximo en un grafo; es decir, un matching con el mayor número de ejes posible. Este problema es uno de los más importantes en la teoría de grafos. Es de gran interés esencialmente por sus aplicaciones en problemas de la vida real como puede ser el problema de asignación de tareas. <br />Comenzaremos dando unas nociones básicas de teoría de grafos y explicaremos detalladamente en qué consiste el problema del máximo matching a la vez que daremos algunos ejemplos. Además, empezaremos particularizando el problema en el caso de los grafos bipartitos. Hallar el máximo matching en un grafo bipartito equivale a resolver un problema de máximo flujo en una red. La demostración del teorema de Hall aplicando el algoritmo de Ford-Fulkerson nos da el procedimiento a seguir para hallar la solución a este problema.<br /> <br />Más adelante, generalizaremos el problema a grafos de todo tipo. Daremos las condiciones que debe cumplir un grafo para tener un matching perfecto, matching en el que participan todos sus vértices. El teorema de Tutte, análogo al de Hall para grafos en general, dice que tenemos un matching perfecto en un grafo G si y solo si el número de componentes impares que tenemos al quitar un conjunto de vértices S al grafo G es menor o igual que el número de vértices de S. Además, veremos una consecuencia de este teorema para el caso particular de los grafos cúbicos. El teorema de Petersen dice que un grafo cúbico y sin puentes tiene un matching perfecto.<br />Finalmente, veremos cómo hallar un matching máximo usando el Algoritmo de Edmonds que se basa en la construcción de árboles alternados. La idea es construir el matching máximo iterativamente a partir de uno dado mejorándolo a través de caminos de aumento y contrayendo, a lo largo de este proceso, los ciclos de longitud impar (blossom) en un solo vértice. El proceso termina dando un camino alternado de aumento o un árbol completo.<br />Estudiaremos también a lo largo del trabajo la complejidad computacional de cada algoritmo, dado que en la práctica estos algoritmos son muy útiles por su implementación y resolución con ayuda de un ordenador, especialmente en el caso de grafos con un elevado número de vértices y ejes.<br /><br /> 000110383 521__ $$aGraduado en Matemáticas 000110383 540__ $$aDerechos regulados por licencia Creative Commons 000110383 700__ $$aGarcía Olaverri, Alfredo$$edir. 000110383 7102_ $$aUniversidad de Zaragoza$$b $$c 000110383 8560_ $$f745395@unizar.es 000110383 8564_ $$s795429$$uhttps://zaguan.unizar.es/record/110383/files/TAZ-TFG-2021-2760.pdf$$yMemoria (spa) 000110383 909CO $$ooai:zaguan.unizar.es:110383$$pdriver$$ptrabajos-fin-grado 000110383 950__ $$a 000110383 951__ $$adeposita:2022-02-10 000110383 980__ $$aTAZ$$bTFG$$cCIEN 000110383 999__ $$a20210625105524.CREATION_DATE