Catálogo de publicaciones

Compartir en
redes sociales


Navegación

Tipo

Acceso

Plataformas

Temática

Mostrando 10 de 4.320 registro(s)

Filtros temática quitar todos

libros Acceso Abierto
Agregar a Mi catálogo

Smooth and F-smooth systems with applications to Covariant Quantum Mechanics

Más información

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere Directory of Open access Books acceso abierto

Cobertura temática: Ciencias naturales - Matemáticas - Educación - Lenguas y literatura  


tesis Acceso Abierto
Agregar a Mi catálogo

Sobre el comportamiento asintótico de soluciones globales en tiempo de ciertas ecuaciones no lineales de evolución

Más información
Autores/as: Claudia Ruscitti ; Oscar Barraza

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 2011 SEDICI: Repositorio Institucional de la UNLP (SNRD) acceso abierto

Cobertura temática: Ciencias naturales - Matemáticas  

Un fluido es un medio continuo, es decir una sustancia que se mueve (se deforma) en forma continua al transcurrir el tiempo, t > 0, y forma un todo continuo en el espacio x = (x1; x2; x3). Pensamos en tal medio como compuesto de partículas puntuales. Desde el punto de vista físico, el concepto de medio continuo es una abstracción que, estrictamente hablando, está en contra de una teoría ampliamente verificada, la teoría atómica. La teoría de los fluidos trata de construir una teoría matemática que sirva de modelo de la realidad; renunciando a la exactitud y teniendo en cuenta la belleza, extensión y profundidad de las matemáticas originadas; y por otra parte desde el punto de vista físico, por su eficacia en reflejar y en permitirnos intuir y conocer la realidad subyacente, explicar su funcionamiento observado y predecir su evolución futura. La aproximación del medio continuo resulta ser tan efectiva que se olvida con frecuencia de que se trata de un modelo. Así, la consideración del fluido como un medio continuo se basa en que éste consiste en un agregado de partículas en movimiento caótico y que la distancia carcterística de este movimiento, que recibe el nombre técnico de \recorrido libre medio entre colisiones", λ, es mucho menor que las longitudes experimentales, de forma que sólo percibimos un cierto promedio de los procesos individuales entre partículas. Una vez establecido que trabajamos en escalas muy superiores al recorrido libre medio de las partículas podemos olvidar el fino detalle de su movimiento individual y ver en torno a cada punto del espacio x y para cada instante t un volumen elemental representativo, δV , de tamaño mesoscópico o medio, mucho mayor que λ¸ y mucho menor que las longitudes macroscópicas en las que deseamos trabajar. Este volumen elemental, que se denomina también partícula fluida, es considerado como un medio continuo y homogéneo; en él se define una velocidad media del movimiento de ese elemento, que será para nosotros la velocidad puntual en este punto e instante, u(x; t). Es decir, suponemos que existe un valor límite de los promedios cuando δV se hace muy pequeño en la escala intermedia. Análogamente, se definen las demás magnitudes macroscópicas, como la densidad y la presión. En este trabajo consideraremos fluidos que no se comprimen, llamados fluidos incompresibles.

tesis Acceso Abierto
Agregar a Mi catálogo

Sobre grafos clique críticos

Más información
Autores/as: Gabriela Susana Ravenna ; Liliana Alcón

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 2019 SEDICI: Repositorio Institucional de la UNLP (SNRD) acceso abierto

Cobertura temática: Matemáticas  

Se llama completo de un grafo a un conjunto de vértices adyacentes entre si; si un completo es maximal con respecto a la inclusión, se dice que es un clique del grafo. Los cliques son estructuras especiales que naturalmente han despertado interés desde el mismo inicio de la Teoría de Grafos. Varios problemas famosos, como por ejemplo el problema de coloración de un grafo, o el problema de satisfabilidad de una fórmula lógica, se han vinculado y formulado en términos de los cliques de un grafo. Por otro lado, existe una gama de problemas motivados en el propio estudio de los cliques de un grafo. Particularmente haremos foco en el estudio del grafo que muestra la relación de intersección entre los cliques: el grafo clique. Dado un grafo H obtenemos el grafo clique de él, (notado K(H)) considerando un vértice por cada clique de H y haciendo dos vértices adyacentes si los correspondientes cliques tienen intersección no vacía. A H se lo llama generador del grafo K(H). ¿Todo grafo es el grafo clique de algún grafo? El artículo de más vieja data en el que se considera esta pregunta es el de Hamelink donde se muestra que no todo grafo es grafo clique, y se da una condición suficiente para que un grafo sea grafo clique: que la familia de sus cliques tenga la propiedad de Helly (toda subfamilia mutuamente intersectante tiene intersección no vacía). A los grafos que satisfacen esta condición les llamaremos grafos clique Helly. Posteriormente Roberts y Spencer, continuando con las ideas de Hamelink, encuentran una condición necesaria y suficiente para que un grafo sea grafo clique: que exista una familia de completos (no necesariamente los cliques) que cubra las aristas del grafo y que tenga la propiedad de Helly. A tales familias las llamaremos familias RS. El problema de determinar la complejidad del reconocimiento de los grafos clique permaneció abierto por más de treinta años, surgiendo en tanto, varias publicaciones al respecto. Se ha probado que tal problema de reconocimiento es NP-completo; y que permanece siendo NP-completo aún restringido a la clase de los grafos split. Siguiendo esta línea de trabajo, se ha desarrollado un algoritmo no polinomial para decidir si un grafo es grafo clique o no; y se ha probado que el problema de reconocimiento de los grafos clique puede reducirse al estudio de los grafos de diámetro 2. Se ha presentado una forma de obtener, a partir de una familia RS de un grafo G, otro grafo tal que su grafo clique sea G. ¿Cuántos generadores tiene un grafo clique? La operación de agregar un vértice v a un grafo H y hacerlo adyacente a todos los vértices de un clique de H nos devuelve un nuevo grafo que tiene la misma imagen que H por K. Se puede concluir que si G es un grafo clique entonces hay infinitos grafos que generan G. Esto motiva la definición de generador crítico, que es un generador minimal respecto a la cantidad de vértices; es decir, H es generador crítico de G si K(H) = G y K(H-v) es distinto de G para todo v perteneciente a H. Es bien conocido que la cantidad de generadores críticos de un grafo clique es finita. ¿Cuáles son aquellos grafos que tienen un único generador critico? Esta pregunta es formulada por primera vez por Escalante, posteriormente fue considerada por los autores Chong-Kean y Yee-Hock. El problema de caracterizar los grafos clique con un único generador crítico permanece abierto. ¿Cuáles son aquellos que generan un completo? Encontramos en la literatura el trabajo de Lucchesi, Picinin de Mello y Szwarcfiter donde se describen los generadores críticos de un completo satisfaciendo tales que no tienen vértice universal y son minimales en el sentido de que no contienen un subgrafo inducido sin vértice universal que genere un completo. Dado un entero positivo p, ¿cuáles son los grafos H tales que K(H) tiene un completo de tamaño p, pero K(H-v) no tiene un completo de tamaño p cualquiera sea el vértice v? En otras palabras, ¿cuáles son los subgrafos prohibidos minimales para la familia K^{-1}(K_p-libre)? Protti y Szwarcfiter estudiaron este problema y describieron mediante subgrafos prohibidos minimales las clases K^{-1}(K_3-libre) y K^{-1}(K_4-libre). Dado un grafo G clique Helly, ¿existe un vértice v en G tal que G-v es también clique Helly? Dourado, Protti y Szwarcfiter se hicieron esta pregunta y conjeturaron que la respuesta era positiva, es decir, todo grafo clique Helly contiene un vértice tal que al removerlo se obtiene nuevamente un grafo clique Helly. A lo largo de la tesis analizamos cada una de estas cuestiones y aportamos resultados originales sobre ellas

tesis Acceso Abierto
Agregar a Mi catálogo

Sobre la aplicación del método de entropía en el estudio de soluciones globales en tiempo de ecuaciones diferenciales de evolución de tipo parabólico

Más información
Autores/as: Laura Langoni ; Oscar Barraza ; María Amelia Muschietti

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 2011 SEDICI: Repositorio Institucional de la UNLP (SNRD) acceso abierto

Cobertura temática: Matemáticas  

Es un hecho conocido la creciente importancia y el amplio campo de aplicación que las ecuaciones en derivadas parciales tienen en la construcción de modelos matemáticos para la descripción de una gran variedad de problemas provenientes de diversas áreas del saber como, por ejemplo, la economía, la física, la biología. Muchos procesos de las ciencias aplicadas se pueden modelar matemáticamente por medio de ecuaciones de evolución. Estas ecuaciones, llamadas ecuaciones de estado, describen los fenómenos físicos a estudio. En las ecuaciones de estado de las teorías matemáticas clásicas intervienen operadores lineales. Sin embargo, algunos de los modelos más complejos utilizados por las distintas ramas de la ciencia involucran ecuaciones diferenciales no lineales. Esto es claro en el caso de la teoría de ecuaciones diferenciales ordinarias y sistemas dinámicos pero en el de las ecuaciones en derivadas parciales no fue siempre así, debido quizás a la ausencia de una teoría general para las mismas. Un motivo por el cual los sistemas no lineales son más difíciles de analizar matemáticamente es que ´estos presentan una serie de propiedades que no muestran las teorías lineales. Por otra parte, las características esenciales de ciertos fenómenos del mundo real que describen las ecuaciones de estado están relacionadas directamente con las propiedades originadas por el carácter no lineal de dichas ecuaciones. Los problemas que típicamente se presentan en el estudios de ecuaciones diferenciales son los relativos a existencia de soluciones locales y globales en tiempo, unicidad de las mismas, regularidad y dependencia de las condiciones iniciales, y comportamiento asintótico, para tiempo grande, de las soluciones globales en tiempo. De esto último será de lo que nos ocuparemos a lo largo de esta tesis.

tesis Acceso Abierto
Agregar a Mi catálogo

Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada

Más información
Autores/as: Nardo Giménez ; Guillermo Matera ; Pablo Solernó

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 2017 Biblioteca Digital (FCEN-UBA) (SNRD) acceso abierto

Cobertura temática: Matemáticas  

La resolución de sistemas de ecuaciones polinomiales y la interpolación polinomial multivariada se analizan desde el punto de vista algorítmico y de la complejidad computacional. Desde el punto de vista algorítmico se exhibe un algoritmo probabilístico que resuelve un sistema polinomial cuya complejidad bit es esencialmente cuadrática en el número de Bézout del sistema y lineal en su talla bit. Este algoritmo resuelve el sistema de entrada módulo un número primo p y aplica levantamiento p–ádico. Para esto, se establecen una serie de resultados sobre la longitud bit de un primo “lucky” p, es decir un primo para el cual la reducción del sistema de entrada módulo p preserva ciertas propiedades geométricas y algebraicas fundamentales del sistema original. Luego este algoritmo se aplica al problema de la interpolación polinomial cuando el conjunto de nodos está dado como el conjunto de ceros de un sistema polinomial, dando como resultado un procedimiento que calcula intepolantes de “bajo grado”. La complejidad bit de estos algoritmos es similar a la de los algoritmos que usan bases de Grobner o H–bases en el peor caso y en ciertos casos de interés práctico puede resultar considerablemente menor. Desde el punto de vista de la complejidad computacional se demuestran cotas inferiores para la complejidad de los problemas de interpolación polinomial. Se introduce un nuevo modelo computacional para la interpolación de Hermite–Lagrange que incluye clases no lineales de interpolantes. Este modelo incluye fenómenos de coalescencia y captura una gran variedad de conocidos problemas y algoritmos de interpolación. En este contexto, se exhiben ejemplos de problemas de interpolación con clases no lineales de interpolantes cuya complejidad es intrínsecamente exponencial, mostrando que nuestro algoritmo para interpolación polinomial multivariada es esencialmente asintóticamente óptimo para los problemas seleccionados y que nada se gana admitiendo no linealidad.

tesis Acceso Abierto
Agregar a Mi catálogo

Sobre la convergencia de métodos de elementos finitos para el modelo de placas de Reissner-Mindlin

Más información
Autores/as: Elsa B. Liberman ; Ricardo Guillermo Durán

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 1995 SEDICI: Repositorio Institucional de la UNLP (SNRD) acceso abierto

Cobertura temática: Matemáticas  

En este trabajo efectuamos un análisis de convergencia de métodos mixtos para el modelo de placas de Reissner-Mindlin, dentro de una teoría general. Esta teoría, que abarca a la mayoría de los métodos conocidos, permitió, no solo dar un marco común para el análisis de los distintos métodos, sino también obtener resultados de convergencia en aquellos casos en que no se disponía de una teoría completa. Los métodos considerados corresponden a elecciones de espacios de elementos finitos que, a pesar de la introducción de la nueva variable, conservan la estructura de desplazamientos del problema. En la Sección 2 se describe el modelo de Reissner-Mindlin, las ecuaciones que define el modelo y resultados que permiten garantizar que, si se escalan convenientemente dichas ecuaciones, las soluciones se mantienen acotadas independientemente del espesor de la placa. En la Sección 3 se consideran resultados de existencia, unicidad y regularidad de soluciones, para problemas generales de tipo mixto. También se considera la ubicación del modelo de placas en dicho contexto, y resultados específicos referidos a la regularidad de las soluciones del modelo de Reissner-Mindlin y su relación con un sistema de ecuaciones más complejo, que incluye dos ecuaciones de Poisson y un sistema de Stokes perturbado. Al comienzo de la Sección 4 se describen las dificultades numéricas que presenta este problema. En el Inciso 4.1 se desarrollan los aspectos generales correspondientes a nuestra teoría. El resultado más importante se presenta en el Teorema 4.4, en el que se dan condiciones suficientes para la convergencia de los métodos de elementos finitos aplicados al modelo de Reissner-Mindlin. Dichas condiciones pueden ser consideradas como una generalización de la propiedad de Fortin entre los espacios de discretización de desplazamientos y esfuerzo de corte. Por otra parte esta propiedad se verifica en muchos ejemplos. En el Inciso 4.2 se definen además condiciones suficientes para la construcción de métodos de elementos finitos convergentes, que generalizan las conocidas para el pro- blema límite (espesor igual a 0). En particular, se analiza la relación que existe entre la definición de los espacios discretos para el modelo de Reissner-Mindlin y los correspondientes a métodos estables para el problema de Stokes. La aplicación de la teoría a varios elementos se ejemplifica en la Sección 5. Los resultados teóricos que definen condiciones generales para la construcción de métodos mixtos convergentes se aplican en los Ejemplos 5.1 y 5.2. Las condiciones mencionadas nos permitieron introducir un nuevo método para grillas triangulares, de orden bajo que es analizado en el Ejemplo 5.1. Para este método se estudia la convergencia y se obtienen estimaciones óptimas del error. En el Ejemplo 5.2 se aplican los resultados de convergencia a un elemento rectangular de orden 2, introducido por Bathe y Brezzi, obteniéndose para este método idénticas estimaciones que las obtenidas por los autores en el caso límite. Cabe mencionar que, con técnicas similares a la utilizadas en este ejemplo, es posible extender los resultados de convergencia a una familia de elementos triangulares de mayor orden, obteniéndose estimaciones óptimas del error. Independientemente, los métodos mencionados fueron objeto de estudio. Allí se propuso también el método analizado en 5.1. El elemento de Bathe-Dvorkin es analizado en el Ejemplo 5.3. Se trata de un elemento para grillas rectangulares de bajo orden. A diferencia de los ejemplos anteriores, en este caso no es posible verificar las hipótesis que garantizan la construcción de métodos convergentes. No obstante, se demuestra la convergencia del método para el caso de redes uniformes utilizando el Teorema 4.4 mencionado previamente. La demostración requiere la utilización de resultados conocidos para el problema de Stokes que se basan en la utilización de técnicas de macroelementos. Las estimaciones del error obtenidas se efectuaron bajo condiciones de regularidad más débiles que las conocidas anteriormente y, como consecuencia de ello, se obtuvieron estimaciones óptimas, con cotas de error independientes del espesor de la placa. En el Ejemplo 5.4 se efectúa la aplicación de la teoría al estudio del método de Arnold-Falk. En este método el desplazamiento transveral es aproximado por elementos no conformes. La demostración de convergencia dada en [2] se basa en la equivalencia de las ecuaciones del modelo de Reissner-Mindlin y el complejo sistema de ecuaciones descripto en la Sección 3, y requiere la demostración de una descomposición discreta de Helmoltz y de la equivalencia entre los correspondientes sistemas discretos. La aplicación de nuestros resultados teóricos proporciona una prueba directa y más simple de la convergencia del método y permite su inclusión dentro del marco general definido por el Teorema 4.4. Finalmente, en la Sección 6, se estudia un método introducido por Zienkiewicz, Taylor, Papadopoulos y Oñate en [26]. Este método fue experimentado numéricamente en [22], pero no se conocían resultados de convergencia. Como consecuencia de nuestro análisis, se demuestra que el método converge con orden óptimo y cotas de error independientes del espesor de la placa. Debido a que la estructura de este método no se corresponde con la de los métodos previamente analizados, la demostración de convergencia se efectúa a través de un análisis comparativo del mismo con el método analizado en el Ejemplo 5.1. Se demuestra que ambos métodos pueden ser identificados, ya que el orden de la diferencia entre sus soluciones es superior al de lo mismos, observándose que la formulación propuesta en el Ejemplo 5.1 es más simple desde el punto de vista de su implementación computacional. El trabajo de comparación se completa, mostrando resultados correspondientes a la experimentación numérica efectuada sobre ambos métodos. Los resultados obtenidos permitieron observar que el comportamiento asintótico de los errores y de la diferencia entre las soluciones de los métodos considerados, predicho por la teoría, se verifica para mallas de cálculo que se utilizan en la práctica.

tesis Acceso Abierto
Agregar a Mi catálogo

Sobre la regularización de determinantes de operadores elípticos

Más información
Autores/as: Oscar Barraza ; Jorge Eduardo Solomín

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 1993 SEDICI: Repositorio Institucional de la UNLP (SNRD) acceso abierto

Cobertura temática: Matemáticas  

Índice: - Sección I: Introducción - Sección II: Lemas de diferenciabilidad de los p-determinantes - Sección III: Relación entre el determinante y los valores de contorno de un problema elíptico - Sección IV: Relaciones entre el ζ-determinante, el determinante de Fredholm y el p-determinante - Sección V: Algunas aplicaciones

tesis Acceso Abierto
Agregar a Mi catálogo

Sobre los fundamentos de la estadística cuántica

Más información
Autores/as: Oscar Alberto Varsavsky

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 1949 Biblioteca Digital (FCEN-UBA) (SNRD) acceso abierto

Cobertura temática: Matemáticas  

El Objetivo general de éste trabajo es reformular la fundamentación estadística de la mecánica cuántica tomando como elementos las "propiedades físicas" en lugar de las magnitudes en general. Procuramos demostrar cuánto más sencillos de demostrar y directamente interpretables aparecen muchos resultados de la mayor importancia, sin que se pierda generalidad. Por supuesto tomamos como punto de referencia el formidable libro de J. von Neumann: "Mathematische Grundlagen der Quantenmechanik", tan lleno de ideas aún no suficientemente explotadas y que es el cimiento obligado de cuanto edificio teórico se ha pretendido levantar en la Mecánica Cuántica. Además de la reformulación antes mencionada, hemos conseguido varios resultados particulares nuevos; entre otros la demostración de que el método Koopman (7) de tratar sistemas dinámicos puede aplicarse a la estadística cuántica, y por lo tanto valen también para ella ciertas demostraciones del teorema ergódico. Hacemos también una verificación del mismo mediante la comparación de una sucesión real de mediciones con una "cadena de Markov" y damos la formulación cuántica del concepto de "transitividad métrica". Hemos también simplificado la demostración de algunos teoremas y en especial generalizado para espectros continuos el referente a la ley de distribución de Maxwell. Exponemos también, aunque sin detalles, dos ideas que nos parecen de gran importancia; la relación topológica entre espacios "complementarios" (coordenadas e impulsos por ejemplo), que aunque implícita en numerosos trabajos no hemos visto nunca enunciada claramente, y la distinción entre el tiempo del sistema y del observador, que permite recobrar la simetría relativista. Nueva es también la comparación entre la lógica propia de las proyecciones, la lógica usual y la de tres valores, y además el concepto de "conjunción estadística" que exponemos en un apéndice. Teníamos también intención de utilizar el concepto estadístico de función característica de una distribución, pero encontramos que ese tema ya había sido tratado, justamente en otro trabajo de tesis, por Arnous (1), en 1947. De todos modos hemos agregado un pequeño apéndice comentando su contenido. En cambio hemos renunciado a la inclusión de un resumen de la parte matemática, pues su volumen estaría fuera de proporción con el resto del trabajo y porque existen obras sumamente claras y apropiadas para referencia, como el capítulo correspondiente del libro de v. Neumann y otras obras que se citan en una bibliografía especial. Aunque por comodidad nuestras fórmulas se refieren concretamente al espacio de Hilbert de las funciones de la clase L² (cuadrado del módulo sumable), valen siempre, con obvias modificaciones, para otros espacios de uso común. Los teoremas que daremos por conocidos pueden encontrarse en su mayor parte en el Capítulo II del libro de v. Neumann, pero en general trataremos de dar referencias explícitas.

tesis Acceso Abierto
Agregar a Mi catálogo

Sobre los grafos VPT y los grafos EPT

Más información
Autores/as: María Pía Mazzoleni ; Marisa Gutiérrez ; Liliana Alcón

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 2014 SEDICI: Repositorio Institucional de la UNLP (SNRD) acceso abierto

Cobertura temática: Matemáticas  

El grafo de intersección de una familia de conjuntos es un grafo cuyos vértices son los miembros de la familia y la adyacencia es definida por la intersección no vacía de los correspondientes miembros. Los grafos de intersección son bastante conocidos y muy estudiados. Algunas clases de grafos definidas como intersección son hereditarias y pueden ser caracterizadas por subgrafos inducidos prohibidos minimales. Los elementos de las familias y las propiedades que las definen aparecen en varios contextos, modelando diferentes situaciones, inclusive de la vida real, lo que es un incentivo adicional para el estudio de estas clases. Ejemplos clásicos son los grafos de intervalos y los grafos cordales. Un grafo de intervalos es el grafo de intersección de una familia de intervalos en la recta real, o, en forma equivalente, el grafo vértice intersección de una familia de subcaminos de un camino. Llamamos Intervalos a la clase formada por los grafos de intervalos. Un grafo cordal es un grafo sin ciclos inducidos de longitud al menos cuatro. Llamamos Cordal a la clase formada por los grafos cordales. Gavril probó que un grafo es cordal si y sólo si es el grafo vértice intersección de una familia de subárboles de un árbol. Ambas clases han sido cuidadosamente estudiadas en la literatura. Con el fin de definir nuevas clases de grafos representadas por subárboles, se imponen condiciones en los árboles, subárboles y en el tamaño de la intersección. Sean h, s y t enteros positivos; una (h,s,t)-representación de un grafo G consiste de un árbol huésped T y una colección (T_v), siendo v un vértice de G, de subárboles de T, tal que: el grado máximo de T es a lo sumo h; todo subárbol T_v tiene grado máximo a lo sumo s; dos vértices v y w son adyacentes en G si y sólo si los correspondientes subárboles T_v y T_w tienen al menos t vértices en común en T. La clase de grafos que tiene una (h,s,t)-representación es denotada [h,s,t]. Cuando no hay restricción en el grado máximo de T o en el grado máximo de los subárboles, usamos h=∞ y s=∞ respectivamente. De ahí que, [∞, ∞,1] = Cordal y [2,2,1] = Intervalos. Las clases [∞,2,1] y [∞,2,2] son llamadas VPT (vertex intersection graph of paths in a tree) y EPT (edge intersection graph of paths in a tree) respectivamente. VPT y EPT son clases incomparables de grafos. Sin embargo, cuando el grado máximo del árbol huésped es tres la clase de los grafos VPT coincide con la clase de los grafos EPT. Los grafos VPT son útiles en muchas áreas, entre las cuales cabe destacar la genética, arqueología y ecología. Los grafos EPT son usados en aplicaciones de redes, donde el problema de planificación de llamadas no dirigidas en una red que es un árbol es equivalente al problema de colorear un grafo EPT. La red de comunicación está representada como un grafo no dirigido de interconexión, donde cada arista es asociada con una conexión física entre nodos. Una llamada no dirigida es un camino en la red. Cuando la red es un árbol, este modelo es claramente una representación EPT. Colorear el grafo EPT de forma tal que dos vértices adyacentes tengan distintos colores, significa que llamadas no dirigidas que comparten una conexión física tienen que planificarse en distintos momentos. En los últimos años, el estudio de las clases [h,s,t] ha merecido varias publicaciones en la literatura. El mínimo t tal que un grafo dado pertenece a [3,3,t] ha sido estudiado. Se ha demostrado que [3,3,1] = Cordal. Los [4,4,2] grafos han sido caracterizados y se da un algoritmo polinomial para su reconocimiento. Las clases [4,2,2] y [4,3,2] han sido estudiadas. La relación entre diferentes clases de grafos de intersección de caminos en un árbol también ha sido analizada. Gravril mostró que el problema de reconocer a los grafos VPT es polinomial. Por otro lado, el reconocimiento de los grafos EPT es un problema NP-completo. Esta Tesis está organizada de la siguiente forma: El Capítulo 2 contiene definiciones que serán utilizadas en los capítulos siguientes y que son necesarias para entender el texto. En el Capítulo 3 nos enfocamos en las clases [h,2,1] para cualquier h>2 fijo; estas son todas subclases de VPT. Caracterizamos a los grafos [h,2,1] usando el número cromático. Mostramos que el problema de decidir si un grafo VPT dado pertenece a [h,2,1] es NP-completo, mientras que el problema de decidir si el grafo dado pertenece a [h,2,1]-[h-1,2,1] es NP-difícil. Ambos problemas permanecen difíciles aún cuando nos restringimos a la clase VPT ∩ Split. Adicionalmente, presentamos una subclase no trivial de VPT ∩ Split en la cual estos problemas son polinomiales. El caso h=2 no es considerado porque [2,2,1]= Intervalos. Nuestros resultados se aplican para cualquier h>2 fijo, pueden ser vistos como una generalización del caso h=3 el cual coincide con la clase [3,2,1]=[3,2,2]= VPT ∩ EPT = EPT ∩ Cordal. Las clases [h,2,1], son cerradas por subgrafos inducidos, de ahí que cada una puede ser caracterizada por una familia de subgrafos inducidos prohibidos minimales. Tal familia es conocida sólo para h=2 y hay algunos resultados parciales para h=3. En este Capítulo asociamos los subgrafos inducidos prohibidos minimales para [h,2,1] que son VPT con los grafos (color) críticos. Describimos cómo obtener subgrafos inducidos prohibidos minimales a partir de los grafos críticos, más aún, mostramos que la familia de grafos obtenida usando nuestro procedimiento es exactamente la familia de subgrafos inducidos prohibidos minimales para [h,2,1] que son VPT. Esta familia junto con la familia de subgrafos inducidos prohibidos minimales para VPT, es la familia de subgrafos inducidos prohibidos minimales para [h,2,1], con h>2. En el Capítulo 4 caracterizamos la clase [h,2,1] por subgrafos inducidos prohibidos minimales para cada h>2 fijo. Cabe destacar que, tomando h=3, obtenemos una caracterización por subgrafos inducidos prohibidos minimales para la clase VPT ∩ EPT = EPT ∩ Cordal=[3,2,2]=[3,2,1]. En el Capítulo 5 damos una nueva condición necesaria para ser un grafo EPT. Para esto nos basamos en la estructura de los cliques de un grafo EPT. Además, encontramos una nueva familia de subgrafos inducidos prohibidos minimales para la clase EPT. En el Capítulo 6 nos enfocamos en los grafos EPT que pueden ser representados en un árbol con grado acotado. Respondemos negativamente una pregunta que Golumbic, Lypshteyn y Stern dejaron abierta, basándonos en la representación EPT que tienen los ciclos de un grafo EPT. Finalmente, en el Capítulo 7, damos algunas conclusiones y analizamos cuáles son los trabajos futuros que nos gustaría realizar.

tesis Acceso Abierto
Agregar a Mi catálogo

Sobre los métodos de resolución aproximada de ciertas ecuaciones de la Físicomatemática

Más información
Autores/as: Manuel Sadosky

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No requiere 1940 Biblioteca Digital (FCEN-UBA) (SNRD) acceso abierto

Cobertura temática: Matemáticas  

Fil:Sadosky, Manuel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.