Homeworks proposti in data 28 Aprile 1998.

• il matching: definizioni.
• il teorema di Berge sui cammini aumentanti.

• Quanti accoppiamenti perfetti contiene un grafo bipartito e completo in funzione del numero di nodi in ciascuna classe di bipartizione? Ed un grafo completo non bipartito?
• Dimostrare che un albero contiene al più un accoppiamento perfetto.
• Trovere un grafo (non bipartito) in cui la massima cardinalità di un accoppiamento sia strettamente inferiore alla cardinalità di una minima copertura per nodi.
• Dimostrare che in una matrice tutta zeri e uni, il minor numero di righe e/o colonne da togliere per eliminare tutti gli uni eguaglia il numero massimo di uni su righe e colonne diverse.

© Dipartimento di Matematica - Università di Trento