• 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
Info
Scarica
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

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

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

Scarica adesso ( PDF - 1 pagine - 15.31 KB )

Documenti correlati

D S M P A G C M G G G D N G G A A G M R , G 14 2019 LA FORMA DEL NEGOZIO FIDUCIARIO IN MATERIA IMMOBILIARE “ ’ ”

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

"#' *"!##!'!//!!##!!,!"" )#!%! " *%)C! "!## %#%'% )%F% '#G-' (% %!"%#!% %""!%(!- ' %, ".!# #!% % F%/!G %"".%&%('%" %!%)C!%" *!

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

1. Sia f : G −→ H un omomorfismo di gruppi. Sia g ∈ G un elemento di ordine m.

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

Dimostrazione. Per ogni g ∈ G il sottogruppo hgi generato da g ` e normale. Sia infatti n l’ordine di g. Se γ ∈ hgi e h ∈ G allora (hγh

Sottogruppi finiti del gruppo moltiplicativo di un campo Maurizio

1. Sia G un gruppo. Poniamo ∆ = {(g, g) : g ∈ G}.

[r]

1. (a) Siano G e H gruppi finiti, e sia f : G → H un omomorfismo suriettivo. Mostrare che f ([G, G]) = [H, H] e che l’indice G : [G, G] `e maggiore o uguale a H : [H, H].

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

stutvwG G xytzwvwG G

[r]

65 1. Idolo del crepuscolo ( ) IN ‐ E ‐ G G

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