Condiciones para que el gráfico bipartito sea plano sin bordes alrededor de los vértices

9

Un gráfico bipartito es plano si no tiene o menores. K 5K3,3K5

Estoy buscando las condiciones necesarias y / o suficientes para permitir dibujos planos sin bordes que "rodeen" conjuntos de vértices. Estos son dibujos satisfactorios:

  1. Todos los vértices de una parte se dibujan en una sola línea vertical. Los vértices de la otra parte se dibujan en una línea vertical paralela.
  2. Los bordes no se cruzan excepto en los vértices.
  3. Los bordes están todos en la franja infinita entre las dos líneas verticales en el punto 1.

Por ejemplo, todos los dibujos aquí, excepto la parte inferior derecha, no son ejemplos. El gráfico inferior izquierdo se puede volver a dibujar para satisfacer las condiciones intercambiando las posiciones de Q y R. Los dos gráficos superiores no se pueden volver a dibujar para satisfacer las condiciones.

ingrese la descripción de la imagen aquí

Los dos gráficos superiores son las únicas obstrucciones que pude encontrar. Mis preguntas son:

  1. ¿Este problema tiene un nombre?
  2. ¿Alguna otra obstrucción que me perdí?
  3. Cualquier pista sobre cómo puedo probar que estas dos obstrucciones (junto con todo lo que me perdí), como menores, por supuesto, son necesarias y suficientes.

Tenga en cuenta que esto no es lo mismo que ser plano externo, es plano externo (se puede dibujar como un cuadrado) pero no se puede dibujar para satisfacer las condiciones que mencioné anteriormente.K2,2

aelguindy
fuente

Respuestas:

13

Sus gráficos son exactamente los gráficos de ancho  de ruta o, de manera equivalente, los bosques, cada uno de cuyos componentes es una oruga . Las orugas tienen dos caracterizaciones relevantes:1

  • son los árboles en los que hay un solo camino que contiene cada vértice de grado más de  ;1

  • son los árboles en los que cada vértice tiene como máximo dos vecinos que no son hojas.

Lema 1. Cada oruga está en tu clase.

Prueba. Deje que sea ​​una oruga y deje que sea ​​una ruta más larga que contenga cada vértice de grado  o más. Tenga en cuenta que, por máxima, . Podemos producir un dibujo de  dibujando primero  como un zig-zag y luego agregando los vértices de grado adyacentes a  entre y  . P = x 1x 2 d ( x 1 ) = d ( x ) = 1 G P 1 x i x i - 1 x i + 1GP=x1x2d(x1)=d(x)=1GP1xixi1xi+1

Lema 2. Cada gráfica en tu clase es acíclica.G

Prueba. Suponga que contiene el ciclo y suponga que tiene un dibujo de la forma requerida. Wlog,  está por encima de  . Pero entonces debemos tener encima de  ya que, de lo contrario, las líneas y  se cruzarían. Por inducción,  está por encima de  para todo y del mismo modo para las  's. Pero entonces cualquier líneaGx1y1x2y2xkykx1x2x1y2y1x1y1x2y2xi+1xii{1,,k1}yykx1debe dejar la región entre las dos columnas de vértices o cruzar cualquier otro borde del ciclo. Esto contradice nuestra suposición de que el gráfico tiene un dibujo adecuado.

Lema 3. No todas las orugas conectadas no están en su clase.

Prueba. Deje que sea ​​un gráfico conectado que no sea una oruga. Si contiene un ciclo, no está en su clase según Lemma  , por lo que podemos suponer que es un árbol. Si no es una oruga, debe contener un vértice  con vecinos distintos , e  , cada uno de los cuales tiene un grado de al menos   .G2xy1y2y32

Supongamos que tenemos un dibujo de  con las propiedades requeridas. Wlog,  está por encima de  y  está por encima de  . Sea un vecino de  . El borde  debe cruzar o  , contradiciendo nuestra suposición de que el gráfico tiene un dibujo de la forma requerida. Gy2y1y3y2zxy2y2zxy1xy3

Teorema. Su clase de gráficos es exactamente la clase de bosques, cada uno de cuyos componentes es una oruga.

Prueba. Deja que sea ​​un gráfico. Claramente, G  está en su clase si, y solo si, cada componente es: si algún componente no se puede dibujar como se requiere, todo el gráfico no puede; Si cada componente se puede dibujar según sea necesario, se puede dibujar todo el gráfico organizando los componentes uno encima del otro. El resultado ahora sigue a Lemmas 13GG13

Corolario. Su clase de gráficos es la clase de gráficos que no tiene o la subdivisión de  K 1 , 3 como menor.K3K1,3

Prueba. Estas son las obstrucciones para el ancho de ruta  1

Estas son esencialmente las obstrucciones que encontró: necesita lugar de K 4 porque este último admitiría K 3 en la clase; La subdivisión de K 1 , 3 es exactamente su segunda obstrucción.K3K4K3K1,3

David Richerby
fuente
Una muy buena respuesta!
Pål GD
0

Entonces, la siguiente respuesta es lo que se me ocurrió:

Como ya mencionó, solo hay dos casos posibles que no se pueden reorganizar.

El segundo caso es no representación correcta si suponemos un gráfico bipartito, ya que Wikipedia define un gráfico bipartito como: cada borde se conecta un vértice en a uno en V .UV

Editar: leí mal el gráfico, lo siento.

Esto nos deja solo con el subgrafo completo , que es la condición que desea evitar. Inversamente, la condición suficiente es que su gráfico bipartito no tenga un subgráfico completo dentro de sí mismo.K2,2

Para probar que cualquier otro subgráfico es válido, puede imaginar lo siguiente:

Primero, suponemos que no tenemos aristas y comenzamos con una arista arbitraria . Al agregar el siguiente borde, tenemos tres casos posibles:e

El primer caso es que tenemos un nodo que no comienza ni termina en el mismo nodo que el primer borde. Esto nos deja sin ningún problema y podemos continuar insertando.

El segundo caso es que tenemos un borde que, en su camino, cruza otro borde ya existente. En este caso, tenemos que intercambiar el vértice o V 2 (el que tiene el borde ya existente) con uno de los nuevos bordes V 3 o V 4 , de modo que sigamos cumpliendo los criterios.V1V2V3V4

Esto supone que no tenemos más bordes que comiencen o terminen en los nodos para intercambiar, lo que nos lleva al siguiente tercer caso: Después de intercambiar uno de los cuatro Vértices , necesitamos rastrear todas las demás conexiones desde el Vértice intercambiado .V1V4

Una vez más, podemos encontrar solo tres soluciones: O rastreamos una conexión final o repetimos el paso que ya dimos antes (rastreando todos los pasos restantes). Si terminamos en un nodo final, podemos intercambiar todos los nodos rastreados.

El último caso posible conducirá a un nodo que ya visitamos, lo que nos dejaría con un subgráfico completo, que luego podemos reducir a la condición mencionada de .K2,2

EDITAR: Para extender esta prueba al segundo caso, tenemos que observar las siguientes condiciones:

En general, si tenemos un subgrafo con al menos un hub (3 o más conexiones), es "bastante fácil".

k>1

Como yo solo tengo un ligero conocimiento en esta área, pero todavía quiero brindarle una posible solución, lo vinculé con un artículo (con suerte) apropiado

Si alguien mencionara este problema, me interesaría aprender, especialmente desde que se me ocurrió esta solución solo siguiendo los pensamientos del teorema de Fáry y subgrafos bipartitos completos.

dennlinger
fuente
¿Cómo es que el segundo caso no es un gráfico bipartito? El borde (H, J) conecta solo H y J y no toca I (es solo que el dibujo es un poco malo).
aelguindy
Ah maldición, pensé que estos eran dos bordes separados. Déjame averiguarlo, pero debería incluirse fácilmente en la prueba actual
dennlinger
k>2
¿Qué quiere decir con "El primer caso es que tenemos un nodo que comienza o termina en el mismo nodo"? No veo cómo su razonamiento prueba las declaraciones. Está demostrando que si hace las cosas de una manera específica, no puede dibujar el gráfico. Ni siquiera veo cómo podría manejar no tener las dos obstrucciones directamente, sino que sus menores de edad ..
aelguindy
El primer caso debería ser "ni ... ni". Lo siento por eso. Y traté de construir una prueba que elimine cualquier subconjunto potencial que viole su condición, verificando todas las ventajas posibles.
dennlinger