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
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 1 … x ℓ 2 d ( x 1 ) = d ( x ℓ ) = 1 G P 1 x i x i - 1 x i + 1 ◻GP=x1…xℓ2d(x1)=d(xℓ)=1GP1xixi−1xi+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íneaGx1y1x2y2…xkykx1x2x1y2y1x1y1x2y2xi+1xii∈{1,…,k−1}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. Gy2y1y3y2z≠xy2y2zxy1xy3□
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 1 y 3 . ◻GG13□
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
Entonces, la siguiente respuesta es lo que se me ocurrió:
Como ya mencionó, solo hay dos casos posibles que no se pueden reorganizar.
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.V1 V2 V3 V4
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 .V1−V4
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".
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.
fuente