DanieleC88
21-04-2009, 16:29
Salve. Ho il testo di un esercizio che recita:
Dato un insieme di intervalli
ℐ = {I(1), I(2), … , I(n)}
dove
I(i) = [s(i), f(i)], s(i), f(i) ∈ R⁺.
Il grafo associato G(ℐ) è definito da V(G) ≔ ℐ e
E(ℐ) ≔ {ij: I(i) ⋂ I(j) ≠ ∅, i ≠ j}.
Questo tipo di grafi si chiamano interval graphs. Dimostrare che non tutti i grafi sono interval graphs.
Ho pensato che "non tutti i grafi sono..." equivale a dire "c'è almeno (esiste) un grafo che non è...", nel qual caso dovrebbe bastarmi mostrare un controesempio. Quindi ho pensato di prendere il caso di un interval graph con un vertice isolato (il quale sarà quindi un'attività senza sovrapposizioni con alcuna altra attività) - chiamiamo i questo vertice - ed aggiungervi un arco e = (i, j) verso un qualsiasi altro vertice j. A questo punto avrei un nuovo grafo G'(ℐ)=(V, E'), il quale è ancora un grafo ma non è un interval graph (poiché l'arco e = (i, j) appena introdotto non ne rispetta la proprietà, avendo I(i) ⋂ I(j) = ∅).
È corretto questo procedimento? Mi sembra troppo banale... :D
ciao e grazie :)
EDIT: infatti era troppo banale, ed il procedimento era sbagliato. Correggo per chi fosse interessato alla soluzione. Come correttamente indicato anche da MathWorld (http://mathworld.wolfram.com/IntervalGraph.html), grafi ciclici con più di 3 vertici non possono essere interval graphs. Ad esempio, se prendiamo un grafo ciclico con 4 vertici (lo potete vedere sempre su MathWorld (http://mathworld.wolfram.com/CycleGraph.html)), troviamo che il primo intervallo si sovrappone al secondo, ed il secondo si sovrappone al terzo: però il terzo intervallo non si sovrappone al primo, e ciò significa che il tempo di inizio della terza attività sarà successivo al tempo di fine della prima. A maggior ragione, quindi, anche la quarta attività ha un tempo di inizio che è sicuramente successivo al tempo di fine della seconda attività, e quindi il tempo di inizio della quarta attività deve essere maggiore o uguale del tempo di inizio della terza, motivo per cui non deve esserci alcun arco che colleghi il quarto vertice al primo (in quanto le due attività non possono sovrapporsi): ma dal momento che il grafo è ciclico, tale vertice è presente, e viola quindi la condizione imposta sugli archi dalla definizione di interval graph.
Questo risultato, ovviamente, è valido anche per grafi ciclici con più di 4 nodi, e la dimostrazione è praticamente identica.
Dato un insieme di intervalli
ℐ = {I(1), I(2), … , I(n)}
dove
I(i) = [s(i), f(i)], s(i), f(i) ∈ R⁺.
Il grafo associato G(ℐ) è definito da V(G) ≔ ℐ e
E(ℐ) ≔ {ij: I(i) ⋂ I(j) ≠ ∅, i ≠ j}.
Questo tipo di grafi si chiamano interval graphs. Dimostrare che non tutti i grafi sono interval graphs.
Ho pensato che "non tutti i grafi sono..." equivale a dire "c'è almeno (esiste) un grafo che non è...", nel qual caso dovrebbe bastarmi mostrare un controesempio. Quindi ho pensato di prendere il caso di un interval graph con un vertice isolato (il quale sarà quindi un'attività senza sovrapposizioni con alcuna altra attività) - chiamiamo i questo vertice - ed aggiungervi un arco e = (i, j) verso un qualsiasi altro vertice j. A questo punto avrei un nuovo grafo G'(ℐ)=(V, E'), il quale è ancora un grafo ma non è un interval graph (poiché l'arco e = (i, j) appena introdotto non ne rispetta la proprietà, avendo I(i) ⋂ I(j) = ∅).
È corretto questo procedimento? Mi sembra troppo banale... :D
ciao e grazie :)
EDIT: infatti era troppo banale, ed il procedimento era sbagliato. Correggo per chi fosse interessato alla soluzione. Come correttamente indicato anche da MathWorld (http://mathworld.wolfram.com/IntervalGraph.html), grafi ciclici con più di 3 vertici non possono essere interval graphs. Ad esempio, se prendiamo un grafo ciclico con 4 vertici (lo potete vedere sempre su MathWorld (http://mathworld.wolfram.com/CycleGraph.html)), troviamo che il primo intervallo si sovrappone al secondo, ed il secondo si sovrappone al terzo: però il terzo intervallo non si sovrappone al primo, e ciò significa che il tempo di inizio della terza attività sarà successivo al tempo di fine della prima. A maggior ragione, quindi, anche la quarta attività ha un tempo di inizio che è sicuramente successivo al tempo di fine della seconda attività, e quindi il tempo di inizio della quarta attività deve essere maggiore o uguale del tempo di inizio della terza, motivo per cui non deve esserci alcun arco che colleghi il quarto vertice al primo (in quanto le due attività non possono sovrapporsi): ma dal momento che il grafo è ciclico, tale vertice è presente, e viola quindi la condizione imposta sugli archi dalla definizione di interval graph.
Questo risultato, ovviamente, è valido anche per grafi ciclici con più di 4 nodi, e la dimostrazione è praticamente identica.