¿T1+T2T1+T2T_1+T_2 es plano si T1,T2T1,T2T_1,T_2 son árboles con los mismos vértices?

Question

¿T1+T2T1+T2T_1+T_2 es plano si T1,T2T1,T2T_1,T_2 son árboles con los mismos vértices?

árboles
Matemáticas
Teoría de grafos
grafos planos
Matemáticas discretas

tstt

tengo dos arboles $T_1=(V,E_1)$ y $T_2=(V,E_2)$ .

Mi pregunta es, suponiendo que $G=(V,E_1\cup E_2)$ , podemos concluir que $G$ es plano?

Creo que es plano, porque $G$ es creado por la union de dos arboles. También leí esta publicación que muestra la unión de dos gráficos planos que no pueden ser planos.

incluirCMath

Sugerencia: existe un criterio para los gráficos planos con respecto al número de aristas.

tstt

Esas condiciones establecen que si

G

$G$ no es más plano, quiero probar que mi gráfico es más plano.

lev

¿Encontrar un contraejemplo?

lev

En realidad, este criterio no lo ayudará, siempre que los conjuntos de vértices sean iguales. Ya que si

| V | = n

$|V|=n$ , entonces la unión de los árboles tendrá como máximo

2 n - 2

$2n-2$ bordes y por lo tanto si

2 n - 2 > 3 n - 6

$2n-2 > 3n-6$ entonces

n < 4

$n < 4$ que siempre será plana.

bof

La unión de los caminos

x, u, y, v, z, w

$x,u,y,v,z,w$ y

u, z, v, x, w, y

$u,z,v,x,w,y$ es el gráfico no plano

K_{3, 3}

$K_{3,3}$ .

bof

Y

K_{3, 4}

$K_{3,4}$ es la unión de dos caminos disjuntos de borde si eso importa.

Respuestas (1)

¿T1+T2T1+T2T_1+T_2 es plano si T1,T2T1,T2T_1,T_2 son árboles con los mismos vértices?

Sugerencia: existe un criterio para los gráficos planos con respecto al número de aristas.
Esas condiciones establecen que si $G$ no es más plano, quiero probar que mi gráfico es más plano.
En realidad, este criterio no lo ayudará, siempre que los conjuntos de vértices sean iguales. Ya que si $|V|=n$ , entonces la unión de los árboles tendrá como máximo $2n-2$ bordes y por lo tanto si $2n-2 > 3n-6$ entonces $n < 4$ que siempre será plana.
La unión de los caminos $x,u,y,v,z,w$ y $u,z,v,x,w,y$ es el gráfico no plano $K_{3,3}$ .
Y $K_{3,4}$ es la unión de dos caminos disjuntos de borde si eso importa.

Misha Lavrov · Answer 1

Misha Lavrov

Una imagen vale mas que mil palabras:

Gravitón

elegante, conciso y visualmente demostrativo. +1

bof

También

K_{3, 3}

$K_{3,3}$ es la unión de dos caminos hamiltonianos. Pero tu ejemplo es mejor porque tus dos árboles son disjuntos.

bof

K_{3, 4}

$K_{3,4}$ es la unión de dos caminos hamiltonianos disjuntos por los bordes.

Misha Lavrov

@bof Esa descomposición de

K_{3, 4}

$K_{3,4}$ es útil en varios casos. A mi asesor le gustaba hacer la siguiente pregunta en una clase de combinatoria de pregrado: si un gráfico contiene dos caminos hamiltonianos de arista disjunta, ¿contiene necesariamente un ciclo hamiltoniano?

K_{3, 4}

$K_{3,4}$ es el contraejemplo más pequeño.

tstt

¿En qué circunstancias podemos concluir que la unión de dos árboles es más plana? Gracias.

Misha Lavrov

@Pop No creo que haya condiciones naturales que nos permitan concluir esto. Si está tratando de hacer esto como un paso de un problema mayor, bueno, ¿qué es lo que está tratando de hacer? Pero probablemente la respuesta será que es necesario un enfoque diferente.

¿T1+T2T1+T2T_1+T_2 es plano si T1,T2T1,T2T_1,T_2 son árboles con los mismos vértices?

tstt

incluirCMath

tstt

lev

lev

bof

bof

Respuestas (1)

Misha Lavrov

Gravitón

bof

bof

Misha Lavrov

tstt

Misha Lavrov

probar el grafo G con n vértices, vértice de grado n−1n−1n-1 y resto de vértices de grado 111 es un grafo de árbol

¿Por qué se utiliza el algoritmo de árbol de expansión para el enrutamiento de puentes?

¿Por qué la homología no puede distinguir entre gráficos planos y no planos?

¿Cómo podemos formalizar la noción de la cara de un gráfico plano?

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

Pruebas que involucran subárboles de un árbol

Suponiendo que G=(V(G),E(G))G=(V(G),E(G))G=(V(G),E(G)) es un gráfico, ¿qué significa Δ(G)Δ (G)\Delta(G) significa?

Gráficos conectados, sin bucles y Multigraphs transitables

NP-completitud del problema de grafos planos no dirigidos

Conexión entre dos árboles

¿T1+T2T1+T2T_1+T_2 es ​​plano si T1,T2T1,T2T_1,T_2 son árboles con los mismos vértices?

tstt

incluirCMath

tstt

lev

lev

bof

bof

Respuestas (1)

Misha Lavrov

Gravitón

bof

bof

Misha Lavrov

tstt

Misha Lavrov

¿T1+T2T1+T2T_1+T_2 es plano si T1,T2T1,T2T_1,T_2 son árboles con los mismos vértices?