Permettere$G$essere un grafo bipartito. Prova che$\alpha(G) = |V(G)|/2$se e solo se G ha un matching perfetto.

Question

Permettere$G$essere un grafo bipartito. Prova che$\alpha(G) = |V(G)|/2$se e solo se$G$ha una corrispondenza perfetta.

$\alpha(G)$è il numero di indipendenza di$G$, cioè , la dimensione del massimo insieme indipendente di$G$.

Non riesco a capire come iniziare questa dimostrazione. Posso vedere che questo è vero guardando l'immaginehttps://i.stack.imgur.com/lV4b9.png, ma non posso formulare la dimostrazione. Se qualcuno potesse aiutarmi a scrivere la prova formale completa, gliene sarei molto grato.

Answer 1

Dato che ho già praticamente dato via la soluzione nei commenti, farò il passaggio in più per completare la dimostrazione. Prova a fare un tentativo ragionevole prima di verificare la soluzione completa:

Permettere$G$essere un grafo bipartito di ordine$n$. Innanzitutto, notalo$G$ha una corrispondenza perfetta$\iff \alpha'(G) = \frac{n}{2}$(questo è ovvio dalle definizioni di corrispondenza perfetta e$\alpha'(G)$). Il teorema di König-Egeváry lo fornisce$\alpha'(G) = \beta(G)$(da$G$è bipartito), mentre un risultato di Gallai lo dà$\alpha(G) + \beta(G)= n$(nessuno di questi è particolarmente difficile da dimostrare, ma non lo farò qui). Combinando quanto sopra, otteniamo$$\alpha(G) = n - \beta(G) = n - \alpha'(G),$$e quindi$$\alpha(G) = \frac{n}{2} \iff \alpha'(G) = \frac{n}{2},$$come doveva essere mostrato.

Answer 2

$(\Longleftarrow)$: Permettere$G$sia un grafo bipartito, quindi da König 1931, Egerváry 1931 , abbiamo che la dimensione di un matching massimo$\alpha'(G)$è uguale alla dimensione di una copertura di vertice minima$\beta(G)$, questo è$$\alpha'(G)=\beta(G)$$Ora, da Gallai 1958, abbiamo$$\alpha(G)+\beta(G)=|V(G)|$$Perciò$$2\alpha(G)=|V(G)|\iff \alpha(G)=\frac{1}{2}|V(G)|$$

puoi continuare da qui alle altre implicazioni?