• Non ci sono risultati.

Si dimostri che l’insieme complementare di un insieme stabile `e sempre una copertura di nodi

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Si dimostri che l’insieme complementare di un insieme stabile `e sempre una copertura di nodi"

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

1.58 Esercizio. Confrontando le figure 1.23 e 1.24 si nota come i due ottimi siano com- plementari. Non `e un fatto casuale. Si dimostri che l’insieme complementare di un insieme stabile `e sempre una copertura di nodi.

Soluzione. Per ogni arco almeno uno dei due estremi non appartiene ad un insieme stabile (altrimenti non sarebbe un insieme stabile) e quindi ogni arco `e incidente ad almeno un nodo del complementare di un insieme stabile, che quindi `e una copertura (il complementare).

Analogamente ogni arco `e incidente ad almeno un nodo di una copertura e quindi nodi del complementare di una copertura non possono essere adiacenti, e allora formano un insieme stabile.

1

Riferimenti

Scarica adesso ( PDF - 1 pagine - 10.48 KB )

Documenti correlati

In un grafo non orientato due nodi sono adiacenti se esiste un arco che li unisce

Grafo particolare è quello "euleriano", dal matematico Eulero, che nel 1736 lo utilizzò per risolvere il problema dei ponti di Königsberg: un cammino o percorso è detto di

Una rete telematica è un insieme di nodi e di connessioni.

Per trasferire un file usando il protocollo ftp occorre avere a disposizione un'applicazione ftp chiamata client ftp (ce ne sono diverse anche di tipo freeware) che viene

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.

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

L L ’ ’ insieme quoziente insieme quoziente

Un caso in cui è rapido verificare l’equivalenza di una relazione è quando la relazione coincide con la relazione d’equivalenza associata ad una funzione.. Si tratta

• Una tri-mesh è un insieme di triangoli adiacenti

[r]

Sia X un insieme

COMPITO DI MATEMATICA DISCRETA Modulo I 22 Giugno

Quante sono le funzioni suriettive da un n−insieme verso un 2-insieme? verso un 3-insieme? e verso un 4-insieme? 1

In quanti modi si possono colorare di rosso e di azzurro i quadretti di una riga di n quadretti in modo che ci siano esattamente c linee di confine fra una zona rossa e una

Insieme canonico

Nel limite (noto come limite termodinamico) l’energia diventa sempre più prossima al suo valore medio e può essere considerata come fissata. Ma questo è nient’altro che il punto