Preclusión coincidente

En la teoría de grafos , una rama de las matemáticas, el número de preclusión de coincidencia de un grafo${\displaystyle G}$, denotado${\displaystyle \mathrm {mp} (G)}$es el número mínimo de aristas cuya eliminación resulta en la eliminación de todos los emparejamientos perfectos o casi perfectos (emparejamientos que cubren todos los vértices excepto uno en un grafo con un número impar de vértices). ^{[ 1 ]} La preclusión de emparejamiento mide la calidad de un grafo como topología de red de comunicaciones para algoritmos distribuidos que requieren que cada nodo del sistema distribuido se empareje con un nodo vecino asociado. ^{[ 2 ]}

En muchos gráficos,${\displaystyle \mathrm {mp} (G)}$es igual al grado mínimo de cualquier vértice en el grafo, porque eliminar todas las aristas incidentes a un solo vértice impide que ese vértice se empareje. Este conjunto de aristas se denomina conjunto de preclusión de emparejamiento trivial. ^{[ 2 ]} Una definición variante, el número de preclusión de emparejamiento condicional , pide el número mínimo de aristas cuya eliminación da como resultado un grafo que no tiene ni un emparejamiento perfecto o casi perfecto ni ningún vértice aislado. ^{[ 3 ] [ 4 ]}

Es NP-completo probar si el número de preclusión coincidente de un grafo dado está por debajo de un umbral dado. ^{[ 5 ] [ 6 ]}

El número de preclusión de coincidencia fuerte (o simplemente, número SMP) es una generalización del número de preclusión de coincidencia; el número SMP de un grafo${\displaystyle G}$, denotado${\displaystyle \mathrm {smp} (G)}$, es el número mínimo de vértices y/o aristas cuya eliminación da como resultado un grafo que no tiene ni emparejamientos perfectos ni emparejamientos casi perfectos. ^{[ 7 ]}

Un gráfico${\displaystyle G}$con un número par de vértices se denomina emparejado máximamente si${\displaystyle \mathrm {mp} (G)=\delta (G)}$, dónde${\displaystyle \delta (G)}$denota el grado mínimo. En tales grafos, algún conjunto de preclusión de emparejamiento trivial (las aristas incidentes a un vértice de grado mínimo) es óptimo. Un grafo se denomina superemparejado si todo conjunto de preclusión de emparejamiento óptimo es trivial. ^{[ 8 ]} Todo grafo superemparejado es máximamente emparejado, pero lo contrario no es necesariamente cierto.

La supercompatibilidad se considera una propiedad deseable para las redes de interconexión , ya que indica que, en caso de fallos aleatorios en los enlaces, es improbable que todos los enlaces fallidos incidan en un único vértice. Se sabe que los grafos hipercubo y sus variantes son supercompatibles. ^{[ 8 ]}

El número de preclusión coincidente puede acotarse para grafos construidos utilizando diversas operaciones de producto de grafos . Para grafos${\displaystyle G}$y${\displaystyle H}$con un número par de vértices: ^{[ 8 ]}

producto cartesiano${\displaystyle G\square H}$:

${\displaystyle \mathrm {mp} (G)+\mathrm {mp} (H)\leq \mathrm {mp} (G\square H)\leq \delta (G)+\delta (H)}$

Si ambos${\displaystyle G}$y${\displaystyle H}$son súper compatibles, entonces${\displaystyle G\square H}$es súper compatible.

Producto de gran calidad${\displaystyle G\boxtimes H}$:

${\displaystyle \mathrm {mp} (G)\mathrm {mp} (H)+\mathrm {mp} (G)+\mathrm {mp} (H)\leq \mathrm {mp} (G\boxtimes H)\leq \delta (G)\delta (H)+\delta (G)+\delta (H)}$

Si ambos${\displaystyle G}$y${\displaystyle H}$son súper compatibles con${\displaystyle \delta (G)\geq 2}$y${\displaystyle \delta (H)\geq 2}$, entonces${\displaystyle G\boxtimes H}$es súper compatible.

Producto directo${\displaystyle G\times H}$:

${\displaystyle \mathrm {mp} (G)\mathrm {mp} (H)\leq \mathrm {mp} (G\times H)\leq \delta (G)\delta (H)}$

Si ambos${\displaystyle G}$y${\displaystyle H}$son súper compatibles con${\displaystyle \delta (G)\geq 2}$y${\displaystyle \delta (H)\geq 2}$, entonces${\displaystyle G\times H}$es súper compatible.

producto lexicográfico${\displaystyle G\circ H}$:

${\displaystyle \mathrm {mp} (H)+\mathrm {mp} (G)|V(H)|\leq \mathrm {mp} (G\circ H)\leq \delta (H)+\delta (G)|V(H)|}$

Si${\displaystyle G}$está emparejado al máximo y${\displaystyle H}$es súper compatible con${\displaystyle \delta (H)\geq 2}$, entonces${\displaystyle G\circ H}$es súper compatible.

Para otras operaciones de grafos binarios , como las operaciones de unión , corona y agrupación, también se han establecido límites en los números de preclusión coincidentes, aunque estas operaciones generalmente no preservan la propiedad de supercoincidencia. ^{[ 8 ]}

Un emparejamiento fraccional es una función${\displaystyle f}$que asigna a cada arista un número en${\displaystyle [0,1]}$de tal manera que${\displaystyle \sum _{e\sim v}f(e)\leq 1}$para cada vértice${\displaystyle v}$donde la suma se toma sobre todas las aristas incidentes con${\displaystyle v}$Un emparejamiento perfecto fraccional es un emparejamiento fraccional .${\displaystyle f}$satisfactorio${\displaystyle \sum _{e\sim v}f(e)=1}$para cada vértice${\displaystyle v\in V(G)}$. Claramente, una correspondencia perfecta es también una correspondencia fraccionaria perfecta, pero lo contrario no es necesariamente cierto. ^{[ 9 ]}

El número de preclusión de coincidencia fraccionaria de un grafo${\displaystyle G}$, denotado${\displaystyle \mathrm {fmp} (G)}$, es el número mínimo de aristas cuya eliminación da como resultado un grafo que no tiene emparejamiento perfecto fraccional. ^{[ 9 ]} Para cualquier grafo${\displaystyle G}$del orden${\displaystyle n}$,

${\displaystyle 0\leq \mathrm {fmp} (G)\leq n-1}$

con ambos límites siendo precisos. Para grafos con un número par de vértices, el número de preclusión de emparejamiento fraccional está acotado por el número de preclusión de emparejamiento ordinario:

${\displaystyle \mathrm {mp} (G)\leq \mathrm {fmp} (G)\leq \delta (G)}$

dónde${\displaystyle \delta (G)}$denota el grado mínimo. En particular, si${\displaystyle G}$es un grafo con un número par de vértices y${\displaystyle \mathrm {mp} (G)=\delta (G)}$, entonces${\displaystyle \mathrm {fmp} (G)=\mathrm {mp} (G)=\delta (G)}$. ^{[ 9 ]}

Para ver los gráficos completos${\displaystyle K_{n}}$con${\displaystyle n\geq 7}$, el número de preclusión de coincidencia fraccionaria es igual a${\displaystyle \mathrm {fmp} (K_{n})=n-1}$. De forma más general, para grafos con un orden par${\displaystyle n\geq 4k+6}$,${\displaystyle \mathrm {fmp} (G)=n-k}$si y solo si${\displaystyle \delta (G)=n-k}$.

Como generalización de la exclusión por coincidencia, el concepto de entero${\displaystyle k}$La exclusión por coincidencia extiende el análisis a los números enteros.${\displaystyle k}$-coincidencias. ^{[ 10 ]} Un número entero${\displaystyle k}$-coincidencia de un gráfico${\displaystyle G}$es una función${\displaystyle h:E(G)\to {0,1,\ldots ,k}}$de tal manera que${\displaystyle \sum _{e\in \Gamma (v)}h(e)\leq k}$para cualquier vértice${\displaystyle v\in V(G)}$, dónde${\displaystyle \Gamma (v)}$denota el conjunto de aristas incidentes con${\displaystyle v}$Un número entero${\displaystyle k}$-combinar es perfecto si${\displaystyle \sum _{e\in \Gamma (v)}h(e)=k}$para cada vértice${\displaystyle v}$y casi perfecto si existe exactamente un vértice${\displaystyle v'}$de tal manera que${\displaystyle \sum _{e\in \Gamma (v')}h(e)=k-1}$y todos los demás vértices satisfacen la condición perfecta. Nótese que el emparejamiento entero 1 coincide con la definición estándar de emparejamiento.

El entero${\displaystyle k}$-número de preclusión coincidente , denotado${\displaystyle \mathrm {mp} _{k}(G)}$es el número mínimo de aristas cuya eliminación da como resultado un grafo que no tiene ni un entero perfecto ni uno casi perfecto.${\displaystyle k}$-coincidencia. El entero fuerte${\displaystyle k}$-número de preclusión coincidente , denotado${\displaystyle \mathrm {smp} _{k}(G)}$es el número mínimo de vértices y/o aristas cuya eliminación da como resultado un grafo que no tiene ni un entero perfecto ni uno casi perfecto.${\displaystyle k}$-coincidencia. Por definición,${\displaystyle \mathrm {mp} _{1}(G)=\mathrm {mp} (G)}$y${\displaystyle \mathrm {smp} _{1}(G)=\mathrm {smp} (G)}$. ^{[ 10 ]}

Para valores pares de${\displaystyle k}$, el entero${\displaystyle k}$El número de preclusión de coincidencia es igual al número de preclusión de coincidencia fraccionaria, ya que un grafo tiene una coincidencia fraccionaria perfecta si y solo si tiene una coincidencia entera perfecta.${\displaystyle k}$-coincidencia cuando${\displaystyle k}$es par. Además, ningún grafo tiene un número entero casi perfecto.${\displaystyle k}$-coincidencia para incluso${\displaystyle k}$Por lo tanto, el análisis normalmente se centra en los valores impares de${\displaystyle k\geq 3}$. ^{[ 10 ]}

Otros números definidos de manera similar mediante la eliminación de aristas en un grafo no dirigido incluyen la conectividad de aristas , el número mínimo de aristas que se deben eliminar para desconectar el grafo, y el número ciclomático , el número mínimo de aristas que se deben eliminar para eliminar todos los ciclos.