Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo
[fórmulas aproximadas, revisar las mismas en el original]Dado un grafo G=(V, E) y un subconjunto S⊆V se define el conjunto P3-intervalo de S como I(S):=S ∪ {v ∈ V: |S∩N(v)| ≥2}. Cuando el conjunto S verifica que I(S)=S , se dice que es P3-convexo. La clase formada por los conjuntos P3-convexos verif...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Tesis doctoral publishedVersion |
| Lenguaje: | Español |
| Publicado: |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
2022
|
| Materias: | |
| Acceso en línea: | https://hdl.handle.net/20.500.12110/tesis_n7049_BlaumAkerman |
| Aporte de: |
| Sumario: | [fórmulas aproximadas, revisar las mismas en el original]Dado un grafo G=(V, E) y un subconjunto S⊆V se define el conjunto P3-intervalo de S como I(S):=S ∪ {v ∈ V: |S∩N(v)| ≥2}. Cuando el conjunto S verifica que I(S)=S , se dice que es P3-convexo. La clase formada por los conjuntos P3-convexos verifica los axiomas que definen una convexidad discreta en V: el conjunto vacío y el conjunto V son P3-convexos, y la intersección de dos conjuntos P3-convexos también lo es. El número de 2-dominación de G es la menor cantidad de elementos de un conjunto S ⊆ V tal que I(S)= V, es decir, tal que todo vértice que no pertenece a S tiene al menos dos vecinos en S . Este parámetro es análogo al bien conocido número de dominación de un grafo. Si se define I^0(S)=S e I^k(S)= I(I^k−1(S )) para k ∈ N, se puede ver que si I^k(S)= I^k+1(S) entonces I^k(S) es la cápsula P3-convexa de S. El número P3-hull de G es la menor cantidad de elementos que tiene un conjunto S cuya cápsula P3-convexa es V, es decir tal que I^k(S)=V para algún k ∈ N0. En la presente tesis nos dedicamos al estudio del número de 2-dominación y del número P3-hull de un grafo desde un punto de vista poliedral, ambos problemas NP-completos en su versión de decisión. A pesar de que las técnicas poliedrales han mostrado su efectividad en la resolución de numerosos problemas de optimización combinatoria, hasta la fecha no se han realizado estudios de este tipo aplicados al cálculo de los parámetros mencionados. Planteamos modelos de programación lineal entera para calcular el número de 2-dominación y el número P3-hull de un grafo, y analizamos distintas propiedades de los poliedros formados por las combinaciones convexas de las soluciones factibles de dichos modelos. Calculamos la dimensión de ambos poliedros, estudiamos la relación que existe entre ellos, presentamos distintas familias de facetas y, por último, brindamos descripciones minimales y completas de los poliedros correspondientes a algunas familias de grafos.[fórmulas aproximadas, revisar las mismas en el original] |
|---|