• Non ci sono risultati.

2.19 Esercizio. Si dimostri che un grafo bipartito ` e perfetto (si tratta dell’esercizio 1.60 formulato diversamente).

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "2.19 Esercizio. Si dimostri che un grafo bipartito ` e perfetto (si tratta dell’esercizio 1.60 formulato diversamente)."

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

2.19 Esercizio. Si dimostri che un grafo bipartito ` e perfetto (si tratta dell’esercizio 1.60 formulato diversamente).

Soluzione. Se in un grafo bipartito esiste almeno un arco, allora certamente χ(G) = 2 e ω(G) =2. Se invece `e totalmente sconnesso tali valori si abbassano ad 1. Siccome ogni sottografo indotto di un grafo bipartito ` e bipartito, la tesi `e dimostrata.

Si noti che il Teorema del Grafo Perfetto permette di affermare il fatto meno ovvio che α(G) = θ(G). Sia C la minima copertura di nodi, e quindi si ha |C| = n − α(G) con n numero di nodi del grafo bipartito. In un grafo bipartito ogni decomposizione in cricche consiste di coppie di nodi adiacenti, cio`e di un accoppiamento, e di nodi singoli.

Sia θ(G) = |M| + |S| dove M `e l’accoppiamento e S `e l’insieme di nodi singoli determinati dalla minima decomposizione in cricche. Siccome n = 2 |M| + |S| si ricava immediatamente

|M| = |C| (tesi dell’esercizio 1.60).

2.21 Esercizio. Dimostrare che un grafo `e bipartito se e solo se tutti i suoi circuiti sono pari.

Soluzione.

Se un grafo `e bipartito (G = (N 1 , N 2 , E)) ogni circuito consiste di una successione alternata di nodi di N 1 e di N 2 e quindi `e pari.

Si supponga che ogni circuito sia pari. Si scelga arbitrariamente un nodo che indichiamo con s. Per ogni altro nodo i tutti i cammini s˜˜˜



i sono tutti pari o tutti dispari per l’ipotesi sui circuiti. Si definisca N 1 l’insieme dei nodi a distanza pari da s e N 2 l’insieme dei nodi a distanza dispari da s. Due nodi i ∈ N 1 e j ∈ N 1 non possono essere adiacenti perch´e esisterebbe un circuito dispari s˜˜˜



i → j˜˜˜



s e similmente per due nodi di N 2 . Quindi il grafo `e bipartito.

1

Riferimenti

Scarica adesso ( PDF - 1 pagine - 22.67 KB )

Documenti correlati

Esercizio 1. Sia M

Universit` a degli Studi di Roma Tre. Corso di Laurea in Ingegneria civile

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

(grafo completo di 3nodi) in cui il massimo accoppiamento ha cardinalit` a 1 e la minima copertura ha cardinalit` a 2.

Per ogni copertura almeno uno dei due nodi accoppiati deve appartenere alla copertura, altrimenti l’arco non sarebbe coperto, da cui la diseguaglianza cercata.. Il pi` u

2.10 Esercizio. Si dimostri che contraendo un grafo partizionato secondo una coloratura minima (numero cromatico) si ottiene un grafo completo.

Se valesse anche nel senso opposto esisterebbe un algoritmo estremamente semplice (e polinomiale) per colorare in modo minimo un grafo (si colora arbitrariamente e si vede se il

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

Si dimostri che il problema del cammino massimo in un grafo (decidere cio`e se esiste un cammino senza ripetizioni di nodi con almeno K archi) `e NP-completo

Si dimostri che il problema del cammino massimo in un grafo (decidere cio`e se esiste un cammino senza ripetizioni di nodi con almeno K archi) `e

Esercizio 1. Si dimostri per induzione su n ∈ N che, per ogni n ≥ 1, vale:

Si terr` a conto non solo della correttezza dei risultati, ma anche della completezza e chiarezza delle spiegazioni..

numero di nodi adiacenti out-degree 26 int *edges

Si assuma che l’input contenga un grafo indiretto, e quindi che per 11 ciascun arco da i a j esiste anche l’arco da j ad i.. 12 Un grafo è connesso quando esiste un percorso tra