OPS > Grafi

PREMESSA

Un grafo si può pensare come l’astrazione di una carta geografica: per esempio il seguente grafo descrive i collegamenti esistenti fra alcune (5) città: queste sono rappresentate da nodi di nome n1, n2, …, n5 e i collegamenti sono rappresentati da segmenti tra i nodi, detti archi.

A ogni arco è associata una lunghezza, come illustrato in figura.

Questo grafo può essere descritto da un elenco di termini, ciascuno dei quali definisce un arco tra due nodi del grafo con la indicazione della relativa distanza in chilometri:

arco(n1,n2,6), arco(n1,n3,5), arco(n1,n5,3), arco(n2,n4,3), arco(n2,n5,2), arco(n3,n4,4), arco(n5,n4,6)

Due nodi si dicono adiacenti se sono collegati da un arco.

Il numero di archi che “escono” da un nodo si dice valenza del nodo; per esempio nel grafo in figura, il nodo n3 ha valenza 2, gli altri hanno valenza 3.

Un percorso (o cammino) tra due nodi del grafo consiste in una sequenza di nodi ciascuno dei quali (tranne l’ultimo) è adiacente con il successivo; un percorso può, quindi essere descritto con una lista di nodi (quelli toccati dal percorso, ordinata dal nodo di partenza al nodo di arrivo).

Per esempio, la lista [n5,n2,n4,n3] descrive un percorso dal nodo n5 al nodo n3; tale percorso ha lunghezza K=2+3+4=9.

Un ciclo è un percorso che inizia e termina nello stesso nodo, per esempio [n5,n2,n1,n5].

Un percorso si dice semplice se non ha nodi ripetuti: un percorso semplice, quindi, non contiene cicli; per esempio [n5,n2,n4,n3] è semplice, mentre [n5,n2,n1,n5,n2,n4,n3] non è semplice perché ha nodi ripetuti.

N.B. Dato un grafo, come quello della precedente figura, è facile scrivere l’insieme di termini che lo descrivono; viceversa, disegnare il grafo da un insieme dei termini è meno ovvio (si vedano i problemi seguenti).

In questo contesto vengono proposti due tipi di problemi: quelli che trattano di percorsi e quelli che trattano di adiacenze.


L’ufficio tecnico di un piccolo comune deve scegliere dove piazzare dei nuovi lampioni.
Il paese di cui si parla può essere pensato come un insieme di piazzette collegate da strade, descritte dal seguente grafo (dove i nodi sono le piazze e gli archi sono le strade):

arco(n5,n1), arco(n6,n8), arco(n3,n6), arco(n4,n3), arco(n8,n1), arco(n2,n8), arco(n4,n2), arco(n6,n7)

Ogni lampione illumina la piazza in cui è collocato, le strade da essa uscenti, e le piazze direttamente collegate alla piazza in cui si trova il lampione.

L’architetto comunale, per motivi estetici, suggerisce di non collocare un lampione nella piazza n6.

Scrivere la lista L, che elenca in ordine crescente i nodi che formano il più piccolo insieme di piazze, che non comprende n6, dove collocare i lampioni per illuminare tutte le piazze del paese.


Un grafo, che si può immaginare come rete di strade (archi) che collegano delle città (nodi), è descritto
dal seguente elenco di archi:

a(n2,n5,1), a(n1,n6,12), a(n1,n2,7), a(n6,n4,1), a(n2,n4,5), a(n5,n1,4), a(n1,n3,3), a(n5,n6,9), a(n3,n5,2)

Disegnato il grafo, trovare:

  1. la lista L1 del percorso semplice più breve tra n1 e n6 e calcolarne la lunghezza K1;
  2. la lista L2 del percorso semplice più lungo tra n1 e n6 e calcolarne la lunghezza K2;
  3. la lista L3 del percorso semplice più breve tra n1 e n6 che non attraversa n2 e calcolarne la lunghezza K3.

L’ufficio tecnico di un piccolo comune deve scegliere dove piazzare dei nuovi lampioni.
Il paese di cui si parla può essere pensato come un insieme di piazzette collegate da strade, descritte dal seguente grafo (dove i nodi sono le piazze e gli archi sono le strade):

arco(n3,n9), arco(n7,n2), arco(n6,n1), arco(n3,n8), arco(n4,n3), arco(n8,n1), arco(n2,n9), arco(n5,n2), arco(n4,n2), arco(n6,n7)

Ogni lampione illumina la piazza in cui è collocato, le strade da essa uscenti, e le piazze direttamente
collegate alla piazza in cui si trova il lampione.
Il sindaco, per risparmiare, vuole utilizzare il minor numero possibile di lampioni, ma vuole allo stesso tempo presentare al consiglio comunale diverse possibilità tra cui scegliere.

Trovate:

  1. Il numero K di modi possibili per illuminare tutte le piazze del paese con il numero minimo di lampioni
  2. La lista L formata da N piazze dove piazzare i lampioni in modo da illuminare tutte le piazze, tale che la somma degli indici dei nodi sia il prodotto di due numeri primi non consecutivi.
    Ad esempio:

    1. La lista [n3,n5,n6,n8] andrebbe bene (se corrispondesse ad un insieme di N piazze su cui porre i lampioni in modo da illuminare tutte le piazze) in quanto la somma degli indici dei nodi è pari a 3+5+6+8=22, e 22 è il prodotto dei due numeri primi 2 e 11 che sono non  consecutivi
    2. La lista [n3,n5,n6,n9] non andrebbe bene in quanto la somma degli indici dei nodi è pari a 3+5+6+9=23, e 23 non è il prodotto dei due numeri primi (infatti 23 è esso stesso un numero primo)
    3. La lista [n1,n5] non andrebbe bene in quanto la somma degli indici dei nodi è pari a 1+5=6, 6 è il prodotto dei due numeri primi 2 e 3, ma 2 e 3 sono consecutivi.

L’ufficio tecnico di un piccolo comune deve scegliere dove piazzare dei nuovi lampioni.
Il paese di cui si parla può essere pensato come un insieme di piazzette collegate da strade, descritte dal seguente grafo (dove i nodi sono le piazze e gli archi sono le strade):

arco(3,6), arco(3,5), arco(6,4), arco(2,5), arco(1,5), arco(5,4), arco(1,2), arco(2,4), arco(3,4)

Ogni lampione illumina la piazza in cui è collocato, le strade da essa uscenti, e le piazze direttamente collegate alla piazza in cui si trova il lampione.
Il sindaco, per risparmiare, vuole utilizzare il minor numero possibile di lampioni, ma vuole allo stesso tempo presentare al consiglio comunale diverse possibilità tra cui scegliere.
Trovare:

  1. Il numero minimo N di lampioni necessari ad illuminare tutte le strade del paese
  2. Il numero K di modi possibili per illuminare tutte le strade del paese con N lampioni
  3. La lista L di N lampioni che, tra tutte quelle che illuminano tutte le strade del paese, risulta avere la più grande somma degli indici delle piazze che la formano.

L’ufficio tecnico di un piccolo comune deve scegliere dove piazzare dei nuovi lampioni.
Il paese di cui si parla può essere pensato come un insieme di piazzette collegate da strade, descritte dal seguente grafo (dove i nodi sono le piazze e gli archi sono le strade):

arco(n4,n6), arco(n4,n2), arco(n8,n1), arco(n6,n8), arco(n3,n6), arco(n5,n7), arco(n2,n8), arco(n6,n7), arco(n5,n1), arco(n4,n3), arco(n8,n3)

Ogni lampione illumina la piazza in cui è collocato, le strade da essa uscenti, e le piazze direttamente collegate alla piazza in cui si trova il lampione. Il sindaco, per risparmiare, vuole utilizzare il minor numero possibile di lampioni.
Trovare:

  1. Il numero minimo N di lampioni necessari ad illuminare tutte le strade del paese
  2. La lista L di N lampioni che illuminano tutte le strade del paese.

Un grafo, che si può immaginare come rete di strade (archi) che collegano delle città (nodi), è descritto dal seguente elenco di archi:

arco(n6,n1,9), arco(n3,n5,5), arco(n6,n2,4), arco(n1,n3,4), arco(n3,n6,3), arco(n1,n2,3), arco(n1,n4,3), arco(n3,n4,2), arco(n5,n2,2), arco(n4,n5,5), arco(n5,n6,2)

Disegnato il grafo, trovare:

  1. La lunghezza minima N1 di un percorso semplice tra n1 e n6;
  2. La quantità K di percorsi semplici tra n1 e n6 di lunghezza N1;
  3. La lista L1 dei nodi che formano il percorso semplice tra n1 e n6 di lunghezza N1 che attraversa il maggior numero di nodi;

La lista L2 del percorso semplice tra n1 e n6 di lunghezza minima tra quelli che attraversano tutti i nodi, e la sua lunghezza N2.


Un grafo, che si può immaginare come rete di strade (archi) che collegano delle città (nodi), è descritto dal seguente elenco di archi:

arco(n1,n2,5), arco(n3,n2,6), arco(n1,n3,7), arco(n4,n5,3), arco(n5,n6,4), arco(n6,n4,8), arco(n2,n5,8), arco(n6,n3,11), arco(n1,n4,5)

Disegnato il grafo, trovare:

  1. la lista L1 del percorso semplice più breve tra n1 e n6 e calcolarne la lunghezza K1;
  2. la lista L2 del percorso semplice più lungo tra n1 e n6 e calcolarne la lunghezza K2.

È dato un grafo descritto dal seguente elenco di archi:

arco(n5,n6,2), arco(n6,n3,3), arco(n3,n4,2), arco(n4,n1,1), arco(n1,n3,4), arco(n2,n5,1), arco(n5,n3,6), arco(n2,n6,4)

Disegnare il grafo e:

  1. trovare la lista L1 del percorso semplice più lungo tra n1 e n2;
  2. trovare la lista L2 del percorso semplice più breve tra n1 e n2.

Un grafo, che si può immaginare come rete di strade (archi) che collegano delle città (nodi), è descritto dal seguente elenco di archi:

arco(n1,n2,4), arco(n4,n6,3), arco(n3,n5,1), arco(n5,n2,2), arco(n6,n5,11), arco(n3,n4,8), arco(n2,n4,4), arco(n1,n3,3)

Disegnato il grafo, trovare:

  1. la lista L1 del percorso semplice più breve tra n1 e n6 e calcolarne la lunghezza K1;
  2. la lista L2 del percorso semplice più breve, tra n1 e n6, che non attraversi n3, e calcolarne la  lunghezza K2.

Un grafo, che si può immaginare come rete di strade (archi) che collegano delle città (nodi), può essere descritto da termini che hanno la struttura:

arco(<nome di nodo>,<nome di nodo>,<distanza>).

È dato il seguente grafo:

arco(n1,n2,4), arco(n3,n2,6), arco(n4,n3,3), arco(n3,n5,2), arco(n5,n4,3), arco(n6,n2,3), arco(n6,n5,5), arco(n6,n4,1), arco(n2,n4,5), arco(n1,n3,10), arco(n6,n3,8)

Disegnato il grafo, trovare:

  1. la lista L1 del percorso semplice più breve tra n1 e n5 e calcolarne la lunghezza K1;
  2. la lista L2 del percorso semplice più lungo tra n1 e n5 e calcolarne la lunghezza K2;
  3. la lista L3 del percorso semplice più breve tra n1 e n5 che attraversi tutti i nodi e calcolarne la lunghezza K3.

Un grafo, che si può immaginare come rete di strade (archi) che collegano delle città (nodi), è descritto dal seguente elenco di archi:

arco(n6,n1,4), arco(n5,n6,2), arco(n3,n4,2), arco(n5,n2,2), arco(n6,n2,4), arco(n3,n5,5), arco(n1,n4,3), arco(n1,n3,4), arco(n3,n6,3)

Disegnato il grafo, trovare:

  1. la lista L1 del percorso semplice più lungo tra n1 e n2 e calcolarne la lunghezza K1;
  2. la lista L2 del percorso semplice tra n1 e n2 che ha lunghezza minima e che attraversi il maggior numero di archi (tra i percorsi di lunghezza minima), e calcolarne la lunghezza K2.
  3. Il massimo valore K3 che risulta essere lunghezza di almeno due percorsi semplici tra n1 e n2
  4. La lista L3 del percorso semplice tra n1 e n2 di lunghezza K3 che contiene l’arco che connette n3 con n5.

Un grafo, che si può immaginare come rete di strade (archi) che collegano delle città (nodi), è descritto dal seguente elenco di archi:

arco(n1,n8,9), arco(n1,n2,2), arco(n2,n3,3), arco(n3,n8,2), arco(n3,n4,12), arco(n7,n8,4), arco(n4,n7,5), arco(n6,n7,3), arco(n4,n5,3), arco(n6,n5,6)

Disegnare il grafo e:

  1. trovare la lista L1 del percorso semplice più lungo tra n1 e n5;
  2. trovare la lista L2 del percorso semplice più breve tra n1 e n5.

Un grafo, che si può immaginare come rete di strade (archi) che collegano delle città (nodi), è descritto  dal seguente elenco di archi:

a(n1,n2,4), a(n3,n2,7), a(n4,n3,5), a(n3,n5,4), a(n5,n4,8), a(n6,n2,6), a(n6,n5,2), a(n6,n3,6), a(n1,n5,12), a(n6,n1,9)

Disegnato il grafo, trovare:

  1. la lista L1 del percorso semplice più lungo tra n1 e n4;
  2. la lista L2 del percorso semplice più breve tra n1 e n4la lista L;
  3. la lisdta L3 del percorso semplice più breve tra n1 e n4 che non passi dal nodo n3.

È dato un grafo descritto dal seguente elenco di archi:

arco(n5,n2,7), arco(n3,n2,9), arco(n1,n2,1), arco(n6,n5,2), arco(n5,n3,3), arco(n6,n2,3), arco(n6,n1,5), arco(n1,n4,4), arco(n2,n4,6)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso più breve tra n3 e n4 e calcolarne la lunghezza K1;
  2. la lista L2 del percorso più lungo (senza passare più volte per uno stesso nodo) tra n3 e n4 e calcolarne la lunghezza K2.

È dato un grafo descritto dal seguente elenco di archi:

arco(n5,n2,7), arco(n3,n2,9), arco(n1,n2,1), arco(n6,n5,2), arco(n5,n3,3), arco(n6,n2,3), arco(n6,n1,5), arco(n1,n4,4), arco(n2,n4,6)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso più breve tra n1 e n3;
  2. la lista L2 del percorso più lungo (senza passare più volte per uno stesso nodo) tra n1 e n3;
  3. trovare il numero N di percorsi diversi da n1 a n3.

È dato un grafo descritto dal seguente elenco di archi:

arco(n5,n7,8), arco(n3,n4,1), arco(n1,n4,2), arco(n6,n3,6), arco(n5,n3,3), arco(n6,n2,6), arco(n6,n4,1), arco(n1,n7,1), arco(n2,n4,8), arco(n1,n3,4), arco(n2,n7,4), arco(n1,n5,7)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso più breve tra n5 e n2 con 4 nodi intermedi;
  2. la lista L2 del percorso più lungo (senza passare più volte per uno stesso nodo) tra n5 e n3.

È dato un grafo descritto dal seguente elenco di archi:

arco(n6,n2,3), arco(n3,n8,2), arco(n1,n5,3), arco(n6,n3,6), arco(n5,n4,1), arco(n7,n2,6), arco(n4,n8,8), arco(n1,n7,1), arco(n2,n4,2), arco(n4,n7,4), arco(n6,n8,3)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso più breve tra n1 e n3 che passa per il nodo n6;
  2. la lista L2 del percorso più lungo (senza passare più volte per uno stesso nodo) tra n1 e n3;
  3. il numero N di percorsi diversi da n1 a n3 che passano per tutti i nodi.

È dato un grafo descritto dal seguente elenco di archi:

arco(n5,n7,8), arco(n3,n4,1), arco(n1,n4,2), arco(n6,n3,6), arco(n5,n3,3), arco(n6,n2,6), arco(n6,n4,1), arco(n1,n7,1), arco(n2,n4,8), arco(n1,n3,4), arco(n2,n7,4), arco(n1,n5,7)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso più breve tra n5 e n2 con 4 nodi intermedi;
  2. la lista L2 del percorso più lungo (senza passare più volte per uno stesso nodo) tra n5 e n3.

È dato un grafo descritto dal seguente elenco di archi:

arco(n6,n2,3), arco(n3,n8,2), arco(n1,n5,3), arco(n6,n3,6), arco(n5,n4,1), arco(n7,n2,6), arco(n4,n8,8), arco(n1,n7,1), arco(n2,n4,2), arco(n4,n7,4), arco(n6,n8,3)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso più breve tra n1 e n3 che passa per il nodo n6;
  2. la lista L2 del percorso più lungo (senza passare più volte per uno stesso nodo) tra n1 e n3;
  3. il numero N di percorsi diversi da n1 a n3 che passano per tutti i nodi.

PROBLEMA 1

È dato un grafo descritto dal seguente elenco di archi:

arco(n1,n2,2), arco(n2,n3,2), arco(n3,n1,5), arco(n4,n1,1), arco(n4,n2,4), arco(n4,n5,3)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso più breve tra n5 e n3 e calcolarne la lunghezza K1;
  2. la lista L2 del percorso più lungo (senza passare più volte per uno stesso nodo) tra n5 e n3 e calcolarne la lunghezza K2.

PROBLEMA 2

Un grafo (che corrisponde alla rete di strade che collegano delle città) è descritto dal seguente elenco di archi:

a(n1,n2,13), a(n1,n4,3), a(n2,n3,3), a(n2,n5,7), a(n3,n4,13), a(n3,n5,11), a(n4,n5,3), a(n5,n1,5)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso semplice più breve tra n1 e n3;
  2. la lista L2 del percorso semplice più lungo tra n1 e n3.

PROBLEMA 3

L’ufficio tecnico di un piccolo comune deve scegliere dove piazzare dei nuovi lampioni.

Il paese di cui si parla può essere pensato come un insieme di piazzette collegate da strade, descritte dal seguente grafo (dove i nodi sono le piazze e gli archi sono le strade):

arco(n1,n2), arco(n2,n3), arco(n3,n1), arco(n4,n1), arco(n4,n2), arco(n4,n5)

Ogni lampione illumina la piazza in cui è collocato, le strade da essa uscenti, e le piazze direttamente collegate alla piazza in cui si trova il lampione.

Trovare:

  1. il numero minimo di lampioni che consente di illuminare tutto il paese;
  2. la lista delle piazze (cioè dei nodi del grafo) su cui collocare tali lampioni, in modo che nessuna piazza sia illuminata da due lampioni.

N.B. la lista deve avere gli elementi in ordine crescente (n1<n2< …<n5).


PROBLEMA 4

Un commesso viaggiatore deve visitare un insieme di città, tornando nel punto di partenza e senza passare due volte per la stessa città (ovvero facendo un tour).

Le distanze tra le coppie di città, in chilometri, sono date dai seguenti termini:

arco(C1,C2,10), arco(C1,C3,4), arco(C1,C4,9), arco(C2,C3,6), arco(C2,C4,5), arco(C3,C4,4)

che hanno la struttura arco(<nome di città>,<nome di città>,<distanza>).

Il commesso parte dalla città C1; disegnare il grafo delle città e trovare la lunghezza, in chilometri del tour più corto.


Il seguente grafo stradale:

può essere descritto dal seguente insieme di termini (ciascuno dei quali definisce un arco tra due nodi del grafo con la indicazione della relativa distanza)

a(n1,n2,2), a(n2,n3,5), a(n3,n4,3), a(n4,n5,4), a(n5,n6,2), a(n6,n1,3), a(n1,n7,8), a(n2,n7,6), a(n3,n7,1), a(n4,n7,9), a(n5,n7,7), a(n6,n7,4)

Un percorso tra due nodi del grafo può essere descritto con la lista dei nodi che lo compongono ordinati dal nodo di partenza al nodo di arrivo.
Per esempio, la lista [n5, n7, n2, n1] descrive un percorso dal nodo n5 al nodo n1 di lunghezza K = 15.

PROBLEMA

Disegnare il grafo stradale corrispondente al seguente insieme di termini (che hanno nome “as” invece di “a”):

as(n8,n2,2), as(n2,n3,6), as(n2,n4,3), as(n9,n3,5), as(n7,n1,5), as(n3,n7,7), as(n4,n7,9), as(n8,n5,10), as(n1,n9,4), as(n6,n1,7), as(n5,n4,6), as(n5,n6,3), as(n6,n7,1), as(n3,n1,15)

Trovare la lista L del percorso più breve fra il nodo n8 e il nodo n9, che passa una sola volta per ciascuno dei nodi del grafo; calcolare la relativa lunghezza K.


Quesito n. 18 – Olimpiadi di Informatica del 2/12/2011