Matching
Def Un matching è un insieme indipendente di archi , ovvero archi che non hanno estremi in comune.
Def Dato un matching in un grafo , l’insieme dei vertici che incidono su un arco del matching vengono chiamati saturati dal matching, o -saturati. I restanti non saturati.
Def Un matching che satura tutti i vertici di un grafo viene detto perfetto.
Analogamente posso definire matching massimali e massimi.
Def Dato un grafo ed un suo matching , un cammino alternante è un cammino in dove gli archi si alternano in archi del matching e non.
Def Un cammino aumentante è un cammino alternante dove il primo e l’ultimo vertice sono non saturati dal matching.
Il motivo di questo nome diviene chiaro col seguente teorema.
Teorema (Berge) Un matching è massimo se e solo se non contiene cammini aumentanti.
Dim
- () Assumiamo che sia un matching massimo, e supponiamo che esista un cammino aumentante. Siccome è aumentante, deve essere pari, e gli archi sono nel matching, mentre gli altri no. Ma allora posso definire un matching migliore che contiene un arco in più:
contraddizione.
- () Assumiamo che non abbia -cammini aumentanti, supponiamo che sia una matching migliore di . Definiamo il sottografo nel seguente modo:
Studiamo qualche proprietà del sottografo. Siccome tutti i vertici di hanno al massimo un arco di e uno di , . Questo significa che ogni componente connessa di è un punto isolato, un cammino, o un ciclo. Se è un ciclo, deve essere pari, infatti non posso avere due archi adiacienti dello stesso matching. Siccome , deve esistere almeno un arco fuori da un ciclo, quindi un cammino con più archi di , quindi deve iniziare e finire con archi in . Ma allora questo cammino è un -cammino aumentante, contraddizione. Quindi non può esistere tale matching migliore , è un matching massimo.