Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






+3 votos
¿Para cualquier gráfica topológica G (unión finita de arcos) conexa, existen dos árboles A y B (gráficas topológicas conexas sin curvas cerradas simples) tales que su unón es G?
por (260 puntos) en Avanzadas
A que te refieres con la union de $A$ y $B$? se vale pegar dos puntos distintos de $A$ en un mismo punto de $B$? Por ejemplo, como descompones la grafica con un vertice y una arista que empieza y termina en el vertice?

1 Respuesta

+1 voto
 
Mejor respuesta
Por las dudas asumiré que las gráficas están inmersas en $\mathbb{R}^3$ (toda gráfica admite tal inmersión). Así queda bien definida la unión de gráficas, como la unión de subconjuntos del espacio. Si esto no satisface la pregunta, sería bueno tener una definición más precisa de la unión de gráficas topológicas.

También asumo que las aristas de $G$ no se intersectan en puntos interiores. De lo contrario la intersección de dos aristas podría tener puntos de acumulación y pareciera que no es el punto de la pregunta.

En términos de la teoría combinatoria de gráficas, no toda gráfica admite tal descomposición; por ejemplo, la completa con 6 vértices (donde cualquier par de ellos son adyacentes) tiene la propiedad que si se separa a las aristas en dos subgráficas, forzozamente en alguna de ellas habrá un triángulo.

Si es permitido considerar parte de una arista en el árbol A y (la cerradura de) el complemento de esa arista en el árbol B, entonces el resultado es cierto.

Llamemos vértices a aquellos puntos que están en el extremo de un arco y no pertenezcan a otro arco (vértices de grado 1), y a aquellos que tengan una vecindad conexa en la que al eliminar el punto se desconecta en al menos 3 componentes (vértices de grado al menos 3). Llamemos aristas a los arcos entre dos vértices que no contengan un tercer vértice.

Sean $A$ y $B$ árboles que contengan a todos los vértices de $G$ (se sabe que existe por uno de los primeros resultados de teoría de gráficas). Si la unión de $A$ y $B$ es $G$, terminamos. Si no, $G \setminus (A \cup B)$ es unión finita disjunta de arcos (aristas), pues $A\cup B$ contiene a todos los vértices. En cada uno de esos arcos $a$ elegimos un punto (interior) $x$ y agregamos arbitrariamente al árbol $A$ el arco de $x$ a uno de los extremos de $a$, y al árbol $B$ el arco de $x$ al otro extremo de $a$. Los conjuntos $A'$ y $B'$ respectivamente obtenidos de $A$ y $B$ tras agregar estos arcos siguen siendo unión finita de arcos, y con las "medias aristas" agregadas claramente no se forman nuevos ciclos. Por lo tanto ambos son árboles y por construcción su unión es $G$.

En términos de gráficas combinatorias, la pregunta es equivalente a la siguiente:

¿Para cualquier gráfica (combinatoria) $G$ conexa, existen dos árboles A y B de una subdivisión $G'$ de $G$ (gráfica obtenida de $G$ sustituyendo aristas por trayectorias) tales que su unón es G'?

La respuesta es sí, y basta subdividir cada arista de $G$ en una trayectoria con dos aristas, aunque en muchos casos es suficiente con menos que eso.
por (2,2m puntos)
seleccionada por
¿Qué es una gráfica topológica?
Bien definido puedes decir que un espacio topológico $G$ es una $gráfica$ si es un poliedro compacto, conexo y 1-dimensional.
Pero puedes pensarlo como la unión finita de arcos.
Ese es precisamente el sentido de la pregunta (perdón por la informalidad) y la prueba me convence, solamente tengo un comentario: ¿No sería necesario que esos árboles $A$ y $B$ que contienen a todos los vértices, sean de tal forma que cada arista de $G$ \ $A \cup B$ tenga al menos un extremo en $A$ y el otro en $B$?.

Ésto para el paso donde a partición de cada arista en $G$ \ $A \cup B$ se le asigna un extremo a $A$ y el otro a $B$. ¿El teorema cubre esa necisdad o pueden construirse $A$' y $B$' a partir de $A$ y $B$ para que eso suceda?
Baron Munchausen definió gráfica topológica en la pregunta y en su comentario (por cierto, la definición de un poliedro topológico dista mucho de lo que los no topólogos entendemos por poliedro y supongo que requeriría definición).

A partir de gráficas, puedes pensar que una gráfica topológica es la gráfica donde consideras como puntos a los vértices y a cada punto de las aristas (cada una es homeomorfa a un arco), con la topología natural. Puedes tomar como base los abiertos en las aristas, y las vecindades de los vértices que incluyen partes no vacías de todas sus aristas incidentes, pero no otros vértices ni puntos de otras aristas.
Para no meterse en problemas lo ideal es pedir que los árboles $A$ y $B$ contengan a todos los vértices (y lo digo en el 6o párrafo). Con la definición que di de vértice, no veo que haya ambigüedad y todo arco de $G\setminus(A\cup B)$ debe pegarle a dos vértices que están tanto en $A$ como en $B$. Tienes razón que si no se pide que los árboles contengan todos los vértices puede fallar la conexidad.
Gracias por la respuesta Daniel, me ha sido de mucha ayuda
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...