Un 2 de borde engañosa gráfico es un gráfico en el que podemos color de los bordes con dos colores, en una forma tal que no hay bordes del mismo color comparten un vértice. Dado un grafo G = (V,E) quiero encontrar un 2 de borde engañosa subgrafo de G que tiene el máximo número de aristas. Actualmente estoy usando este algoritmo. Me parece un tamaño máximo de coincidencia de M1 en G y me encuentro con un tamaño máximo de coincidencia M2 en G - M1. Me gustaría demostrar que este algoritmo puede concederme un 3/4 aproximación de este problema. Alguien me puede ayudar demostrando que?
Respuesta
¿Demasiados anuncios?
Cada una de las $2$ borde engañosa subgrafo $H$ $G$ es una unión de vértices distintos caminos o ciclos de longitud. Deje $H$ ser de un tamaño máximo $2$ borde engañosa subgrafo $H$ de $G$, $m=|E(H)|$, y $M_1$ ser de un tamaño máximo de coincidencia en $G$. Ya que cada monocromática conjunto de aristas constituye una coincidencia, $m_1=|M_1|\ge |E(H)|/2=m/2$. Siguiente, desde un subgrafo de un $2$ borde engañosa gráfico es $2$ borde engañosa, en el conjunto de $E(H)\setminus M_1$ podemos encontrar una coincidencia de tamaño, al menos,$|E(H)\setminus M_1|/2$. Entonces $$m_1+m_2=|M_1\cup M_2|\ge m_1+|E(H)\setminus M_1|/2\ge $$ $$m_1+(m-m_1)/2=(m+m_1)/2\ge (m+m/2)/2=3m/4.$$
