• Non ci sono risultati.

e quindi α(L(G)) = θ(L(G)) = 1 mentre l’accoppiamento massimo in G ha cardinalit` a 1 e la minima copertura di nodi in G ha cardinalit` a 2.

N/A
N/A
Protected

Academic year: 2021

Condividi "e quindi α(L(G)) = θ(L(G)) = 1 mentre l’accoppiamento massimo in G ha cardinalit` a 1 e la minima copertura di nodi in G ha cardinalit` a 2."

Copied!
1
0
0

Testo completo

(1)

2.15 Esercizio. Si dimostri che in un grafo G un accoppiamento ha la stessa cardinalit` a di una copertura di nodi se e solo se α(L(G)) = θ(L(G)). Ad esempio nei grafi di figura 2.13 si ha l’eguaglianza,mentre nei grafi di figura 2.14 si ha la diseguaglianza.

Soluzione. A dire il vero l’implicazione `e vera solo in un senso,cio`e che l’uguaglianza in G implica l’uguaglianza in L(G). Infatti un insieme stabile in L(G) `e un insieme di archi in G non incidenti fra loro,ovvero ` e un accoppiamento in G,e viceversa. Quindi determinare α(L(G)) `e equivalente a determinare il massimo accoppiamento in G. Ogni nodo i in G d` a luogo in L(G) ad una cricca i cui nodi sono gli archi di G incidenti in i. Quindi una copertura di nodi in G diventa una decomposizone in cricche in L(G).

Per` o non `e detto che una decomposizione in cricche in L(G) corrisponda ad una coper- tura di nodi in G. Infatti in L(G) possono essere presenti delle cricche di tre nodi provenienti da tre archi disposti a cricca in G e non necessariamente incidenti nello stesso nodo. Ad esem- pio se G = K

3

si ha che L(G) = K

3

e quindi α(L(G)) = θ(L(G)) = 1 mentre l’accoppiamento massimo in G ha cardinalit` a 1 e la minima copertura di nodi in G ha cardinalit` a 2.

1

Riferimenti

Documenti correlati

(b) Le classi di equivalenza sono tre: l’elemento neutro, la classe delle trasposizioni e la classe dei

Sottogruppi finiti del gruppo moltiplicativo di un campo Maurizio

[r]

Inoltre G contiene il coniugio complesso, che lascia fisse le tre radici reali e scambia le

L’incontro è aperto alla partecipazione di docenti universitari, avvocati, tirocinanti, studiosi e operatori

L’appoggio bipodalico statico mostra le pressioni plantari esercitate dal paziente in 100 livelli per evidenziare le differenti intensità di carico in percentuale della

[r]

Difatti  il  Professor  Henry  Faber,  padre  di  Sam  e  noto  scienziato