Particion en triangulos

Partici´n en Tri´ngulos o a
Nicol´s Rodr´ a ıguez Celys??,??
Departamento de Ingenier´ de Sistemas y Computaci´n ıa o Universidad de los Andes C´digo:200415259 o Bogot´, Colombia a

Resumen Este trabajo consiste en analizar el problema de partici´n en tri´ngulos (PT) o bien conocido en ingles o a partition into triangle. Se introduce la notaci´n de un grafo para definir el problema PT. Sedemuestra que o PT es un problema NP completo por medio de un algoritmo de validaci´n y reducci´n del problema X3C. o o Se muestra dos aproximaciones voraces del problema hechas por Hassin y Rubestein para MPT (m´xima a partici´n de tri´ngulos) y otra hecha por Baker a tr´ves de la implementaci´n de outerplanars a (PT). o a a o Palabras Clave: Problema Np, Np completo, Grafo, Grafo con peso.

1Introducci´n o

Los problemas Np-completo son de arduo an´lisis puesto que los algoritmos que a resuelven estos problemas se ejecutan en tiempos exponenciales. Una instancia de estos problemas es el problema Partici´n de Tri´ngulos. Partici´n de Tri´ngulos es o a o a ampliamente aplicado en la ingenier´ gr´fica, siendo el triangulo es el pol´ ıa a ıgono con menos demanda de memoria implicando unan´lisis de mayor eficiencia sobre los a objetos gr´ficos de alta demanda, siendo as´ uno de los problemas mas estudiados en a ı la ingenier´ de computaci´n. El objetivo principal de este trabajo es presentar el ıa o problema Partici´n de Tri´ngulos, demostrar que este es un problema Np-completo o a y mostrar aproximaciones voraces (soluciones algoritmias que se ejecutan en tiempo polinomial) alproblema.

2

Definiciones de un Grafo

En esta secci´n se presentan unas definici´n del grafo para uso a lo largo de este o o texto.
1 2

Gracias a todo lector que lea este documento Email: n-rodri1@uniandes.edu.co

Rodr´ ıguez Celys

Definici´n 2.1 un grafo se denota como G = (V, E) donde V es el conjunto de o v´rtices vi tal que V = {v1 , v2 , ...., vn }, y E es un conjunto de arcos elcual es e subconjunto de la relaci´n V × V tal que cuando vi , vp ∈ E se dice que hay un o arco en el grafo G que va del v´rtice vi al v´rtice vp . e e

3

Definici´n del problema partici´n en tri´ngulos o o a

A continuaci´n se dar´ una definici´n del problema partici´n en tri´ngulos seguido o a o o a de una descripci´n gr´fica del problema. Conociendo la notaci´n de grafos (ver o a o definici´n??) se define el problema partici´n en tri´ngulos. o o a Definici´n 3.1 Un problema es partici´n en tri´ngulos si dado un grafo G = (V, E) o o a donde |V | = 3q (el numero de v´rtices es m´ltiplo de 3) para un q entero positivo, e u tiene como pregunta: ¿hay una partici´n del conjunto V en q conjuntos disjuntos o de v´rtices V1 , V2 , ...., Vq tal que cada conjunto Vi tiene tres v´rtices delconjunto e e V (Vi = vi,[1] , vi,[2] , vi,[3] ) tal que para cada v´rtice del conjunto Vi esta conectado e con los restantes v´rtices del conjunto Vi por medio de arcos que pertenecen a e E( vi,[1] , vi,[2] , vi,[3] , vi,[2] , vi,[1] , vi,[3] ∈ E)? A manera de ejemplo, en la figura ?? podemos detallar el problema partici´n en o tri´ngulos especificado en la definici´n(??). En la figura ??.a vemos unainstancia a o del problema donde hay 12 v´rtices y se puede deducir que q es igual a 4. Siendo e as´ un certificado a este problema se muestra en la figura ??.b donde hay los q ı, conjuntos V1 = {v1 , v2 , v3 } , V2 = {v4 , v5 , v9 } , V3 = {v6 , v7 , v8 } , V4 = {v11 , v10 , v12 } diferenciados entre si por los colores amarillo, azul, verde y rojo respectivamente. Note que estos conjuntos son disjuntos yla uni´n de estos forman al conjunto de o v´rtices V . Ademas note que en cada conjunto, todo v´rtice esta conectado por e e medio de un arco (que pertenece a E) con los otros v´rtices del mismo color. e

(.a)Instancia

(.b)Certificado

Fig. 1. Ejemplo problema partici´n en triangulos o

4

El problema Partici´n en tri´ngulos pertenece a la o a clase de los problemas NP-completos

En...