Matroides y rigidez de grafos

Abstract

RESUMEN: En este trabajo se estudia el concepto de matroide y sus distintas definiciones, deduciendo ideas útiles, así como la rigidez de grafos, comprobando resultados equivalentes a la independencia y rigidez, tanto genérica como en una posición dada, y sus propiedades de invariancia. Después se definen las matroides de rigidez, con las que se puede resolver el problema de la rigidez en 1 y 2 dimensiones, y se encuentran caracterizaciones equivalentes a esa rigidez y algoritmos para decidirla. Finalmente, se estudia de forma análoga la rigidez de grafos con sólidos rígidos en vez de puntos en los vértices.

ABSTRACT: In this project the concept of a matroid and its different definitions are studied, deducing useful ideas, as well as rigidity of graphs, proving results equivalent to independence and rigidity, both generic and in a given position, and invariance properties. Then rigidity matroids are defined, with which the rigidity problem in 1 and 2 dimensions can be solved, and we find equivalent characterizations to this rigidity and algorithms to decide it. Finally, I study in a similar way the rigidity of graphs with rigid bodies instead of points in the vertices.