Abbiamo notato che ogni grafo Sona diverso dal grafo vuoto `e un grafo gaussiano. Mo- striamo ora che ogni grafo gaussiano `e isomorfo ad un grafo Sona, ottenendo quindi la sostanziale identit`a tra le due nozioni. Lo faremo mostrando dapprima che il grafo con- tenente un unico vertice e due loop `e un grafo Sona. Le operazioni di eliminazione di un vertice e di introduzione di un vertice descritte sopra per i grafi gaussiani possono essere applicate ad un grafo Sona in quanto grafo gaussiano. Mostreremo quindi che i grafi ottenuti da tali operazioni sono isomorfi a grafi Sona.
Il primo passo `e semplice, infatti il grafo Sona che si ottiene dall’unica linea di R(4, 2) `
e il grafo contenente un unico vertice e due loop (Figura 3-1).
Figura 3-1: R(4, 2).
Passiamo adesso alla prima operazione, l’eliminazione di un vertice. Consideriamo un grafo Sona G derivato da una linea di R(2p, 2q). Introduciamo nel punto ammissibile autointersezione della linea corrispondente al vertice v da eliminare uno specchio orientato in modo da non spezzare la linea. Si ottiene un grafo Sona G1 con un vertice in meno. `E
facile vedere che l’operazione di eliminazione di un vertice produce un grafo G|v isomorfo
a G1.
Per l’operazione di introduzione di un vertice le cose non sono cos`ı semplici. Il caso ideale `e il caso in cui ci sia uno specchio in un punto dove tutti e quattro i segmenti ammissibili siano percorsi dalla linea ed appartengano ai due rami che intendiamo inter- secare per ottenere il nuovo vertice, e togliendo lo specchio si abbia un’autointersezione (questo `e vero ovviamente solo se i due rami della linea sono co-orientati, altrimenti la linea si spezzer`a). In generale non troveremo questa situazione ideale. Vedremo per`o che sar`a possibile ricondurci ad essa utilizzando alcune tecniche. In ognuna di queste tecniche sostituiremo la griglia e la linea di partenza con una nuova griglia ed una linea su di essa in modo che i grafi Sona derivati dalle due linee siano isomorfi.
Faremo l’ipotesi non restrittiva che nella griglia considerata in partenza non ci siano specchi oltre a quelli incontrati dalla linea che ci interessa.
Data una linea, chiamiamo adiacenti due punti ammissibili connessi tramite un seg- mento ammissibile percorso dalla linea. Allo stesso modo chiamiamo adiacenti due segmenti ammissibili visitati dalla linea e incidenti su uno stesso punto ammissibile.
Chiameremo spigolo di una linea un punto ammissibile visitato dalla linea dove `e presente uno specchio.
Data una linea ed un segmento ammissibile S da essa visitato, chiameremo S1−, o precedente ad S, l’ultimo segmento ammissibile visitato dalla linea prima di visitare S,
chiameremo S1+, o successivo ad S, il segmento visitato dalla linea subito dopo S. Ana-
logamente S2− = (S1−)1− sar`a il segmento precedente a S1−, e cos`ı via. Considereremo
il primo segmento della linea come il successivo dell’ultimo segmento, allo stesso modo considereremo l’ultimo segmento come il precedente del primo.
Consideriamo un segmento T di una linea tale che T e T1− siano sulla stessa retta
e il punto ammissibile V dove T e T1− sono incidenti non sia un’autointersezione della
linea. Ci saranno due regioni del piano delimitate dalla linea tali che T si trovi sul loro bordo. Consideriamo una di esse. Chiamiamo (aT, bT) l’incremento che viene usato nel costruire T . Abbiamo che il verso di costruzione di T , ovvero (aT, bT), pu`o essere concorde oppure discorde rispetto all’orientazione della regione considerata. Abbiamo inoltre due possibilit`a, aTbT = 1 oppure aTbT = −1. Si verifica che, ponendo uno specchio in V , il
segmento successivo a T1− sar`a interno alla regione che ci interessa nei seguenti casi.
• Ponendo uno specchio orizzontale se aTbT = 1 e (aT, bT) `e discorde con l’orienta-
zione della regione.
• Ponendo uno specchio orizzontale se aTbT = −1 e (aT, bT) `e concorde con l’orien-
tazione della regione.
• Ponendo uno specchio verticale se aTbT = −1 e (aT, bT) `e discorde con l’orientazione
della regione.
• Ponendo uno specchio verticale se aTbT = 1 e (aT, bT) `e concorde con l’orientazione
della regione.
Chiamiamo corretto l’orientamento dello specchio che verifica le condizioni appena defi- nite.
Introdurre un vertice per un grafo Sona ci porta, in generale, a dover considerare una griglia pi`u grande di quella di partenza. Per aggiungere un vertice dobbiamo portare la linea ad autointersecarsi in un punto interno alla regione che ci interessa. Per poterlo fare in generale dobbiamo quindi avere punti ammissibili interni ad una qualsiasi regione delimitata dalla linea e questo non `e sempre vero. Possiamo ovviare al problema dilatando la griglia.
Dilatazione della griglia. Consideriamo la griglia R(2p, 2q) con n specchi interni posti in S1 = (x1, y1), ..., Sn= (xn, yn). In R(2p, 2q) consideriamo la linea A che parte da
Definiamo Γj : R2 → R2, Γ(x, y) = (jx, jy), con j intero dispari maggiore di uno.
Consideriamo adesso R(2jp, 2jq). Notiamo che se P `e un punto ammissibile di R(2p, 2q) allora Γj(P ) `e un punto ammissibile di R(2jp, 2jq). Posizioniamo in Γj(Si) =
(jxi, jyi), ∀i ∈ {1, ..., n}, uno specchio con lo stesso orientamento dello specchio di
R(2p, 2q) posto in Si. Consideriamo adesso la linea Γj(A) di R(2jp, 2jq) che parte da
Γj(Q) con incremento iniziale (a, b) (Figure 3.2(a) e 3.2(b)).
`
E facile vedere allora che la linea Γj(A) passa per tutti i punti Pi di R(2jp, 2jq) del
tipo Γj(Pi) con Pi punto ammissibile di R(2p, 2q) visitato dalla linea A. Inoltre le due
linee visitano questi punti nello stesso ordine. Di conseguenza i punti ammissibili che sono autointersezioni della linea A vengono mandati tramite Γj in tutti e soli i punti che
sono autointersezioni della linea Γj(A).
Si hanno dunque le seguenti propriet`a.
• I grafi Sona derivati da A e da Γj(A) sono isomorfi.
• Le regioni del piano delimitate dalla linea A possono non avere punti ammissibili interni.
• Le regioni del piano delimitate dalla linea Γj(A) hanno sempre punti ammissibili
interni.
Vediamo adesso come spostare gli spigoli che potrebbero crearci problemi.
Ribaltamento di spigoli. Sia A una linea e P uno spigolo. Possono aversi diversi casi a seconda se nei punti adiacenti allo spigolo siano presenti o meno specchi ed au- tointersezioni. Considereremo il solo caso in cui nei punti ammissibili adiacenti a P non siano presenti n´e specchi n´e autointersezioni poich´e possiamo sempre ricondurci ad esso dilatando la griglia. Sposteremo il percorso della linea nel seguente modo. Consideriamo lo spigolo P e i punti ammissibili adiacenti a P . Chiamiamo P1 e P2 due punti adiacenti
a P posti su uno stesso ramo della linea, P3 e P4 quelli posti sull’altro ramo della linea,
se esistente, passante per P dalla parte opposta dello specchio rispetto al primo ramo. Consideriamo inoltre l’unico punto ammissibile P5 che potrebbe essere adiacente a P1 e
P2 oltre a P (l’ultimo vertice del quadrato dove gli altri vertici sono P , P1 e P2). Se
esistenti P3 e P4 consideriamo anche l’unico punto ammissibile P6 che potrebbe essere
(a) Linea con punto iniziale (0, 1) di R(10, 6) con specchi orizzontali in (1, 2), (5, 4), (9, 2), (9, 4) e specchi verticali in (2, 3), (3, 2), (6, 3).
(b) Abbiamo preso j = 5. Linea con punto ini- ziale (0, 5) di R(50, 30) con specchi orizzontali in (5, 10), (25, 20), (45, 10), (45, 20) e specchi verticali in (10, 15), (15, 10), (30, 15).
(c) Abbiamo preso j = 3. Risultato del ribaltamento degli spigoli posti in (9, 6) e (15, 18). Linea con punto iniziale (0, 3) di R(30, 18) con specchi orizzontali in (3, 6), (27, 6), (27, 12), (14, 17), (15, 16), (16, 17), (15, 12), e specchi verticali in (6, 9), (7, 6), (8, 5), (8, 7), (10, 5), (10, 7), (11, 6), (18, 9).
P6 se esistenti) con lo stesso orientamento dello specchio in P e, a meno che non sia su
una parete, eliminiamo lo specchio in P . Nel caso P = Q = (xA, yA) fosse il punto di
partenza della linea A, dovremo far partire la linea da Q1 = (xA+ 1, yA+ 1). Si avr`a
Q1 = P1 oppure Q1 = P2.
Con questa nuova configurazione di specchi la linea non passer`a pi`u per P ma al suo posto passer`a per P5 (ed eventualmente P6) (Figura 3.2(c)). I due grafi Sona derivati
sono tra loro evidentemente isomorfi.
Possiamo notare che con questa tecnica risolviamo il seguente problema. Ammettia- mo che ci sia una regione delimitata da una linea dove in uno spigolo tutti i segmenti ammissibili incidenti sono visitati dalla linea. In quel punto la regione viene chiusa ma, nel grafo Sona corrispondente, ad uno spigolo non corrisponde un vertice. Gli archi del grafo corrispondenti ai due rami (o l’arco corrispondente al ramo, se unico) della linea passante per lo spigolo perci`o delimiteranno (delimiter`a, se un solo ramo) una regione i cui punti interni sono divisi tra due (o pi`u) regioni non connesse. Applicando il ribal- tamento a tutti gli spigoli dove i segmenti ammissibili incidenti sono tutti visitati dalla linea, otteniamo la propriet`a che, nel grafo Sona corrispondente, l’interno di ogni regione delimitata dagli archi del grafo `e una regione connessa.
Andiamo adesso a definire la tecnica che ci consentir`a di “avvicinare” i due rami della linea che vogliamo intersecare per aggiungere un nodo nel grafo Sona corrispondente. Dovremo preliminarmente controllare che nella frontiera della regione che ci interessa non ci siano spigoli dove tutti i segmenti ammissibili incidenti siano visitati dalla linea (4 per i punti interni e due per i punti sulle pareti, nel caso la regione che ci interessa sia quella esterna). Applichiamo la tecnica del ribaltamento degli spigoli nei punti dove questo accade.
Avvicinamento di due segmenti non adiacenti di una linea posti sul bordo di una stessa regione. L’idea `e quella di deviare un tratto della linea e fare in modo che proceda parallelamente al bordo della regione che ci interessa fino a giungere di fronte al secondo tratto della linea che ci interessa. Per essere sicuri che il procedimento non trover`a intoppi applichiamo preliminarmente la tecnica di dilatazione della griglia con j = 7.
Consideriamo un segmento ammissibile S che si trovi nel primo tratto della linea che ci interessa. Richiediamo che S2−, S1−, S, S1+ e S2+ si trovino su una stessa retta e
non ci siano autointersezioni nei punti dove sono incidenti due dei segmenti considerati. Consideriamo un secondo segmento R non adiacente ad S, posto nel secondo tratto della linea che ci interessa. Richiediamo che R2−, R1−, R, R1+ e R2+ si trovino su una stessa
retta e non ci siano autointersezioni nei punti dove sono incidenti due dei segmenti consi- derati. Siamo sicuri di trovare un tale S ed un tale R grazie alla dilatazione della griglia di j = 7 fatta preliminarmente. Vogliamo sostituire S e R con due nuovi tracciati della linea fatti di segmenti interni alla regione che ci interessa e ottenuti aggiungendo un cer- to numero di specchi alla griglia. Vogliamo pi`u precisamente trovare M = {R1, R2, R3}, N = {S1, ..., Sk}, dove Ri+1 = (Ri)1+ per ogni i ∈ {1, 2}, Si+1 = (Si)1+ per ogni
i ∈ {1, ..., k − 1}, R1 = (R1−)1+, R3 = (R1+)1−, S1 = (S1−)1+ e Sk = (S1+)1−. Vogliamo inoltre che M ed N abbiamo uno spigolo in comune (Figura 3-3).
(a) (b) (c)
Figura 3-3: Esempi.
Procediamo a definire M . Poniamo uno specchio con orientamento corretto nel punto ammissibile tra R1− e R e chiamiamo tale specchio W1. Poniamo inoltre nel punto ammissibile tra R e R1+ uno specchio W2 con orientamento opposto a quello di W1.
Otteniamo che la linea, dopo aver visitato W1−, passer`a a visitare un segmento interno
alla regione che ci interessa. Chiamiamo tale segmento R1. Nel secondo estremo di
R1 visitato dalla linea poniamo uno specchio W3 con lo stesso orientamento di W1. Il
segmento R2 visitato successivamente sar`a quindi parallelo ad R. Nel secondo estremo
di R2 visitato dalla linea poniamo uno specchio W4 con lo stesso orientamento di W2.
Otteniamo che la linea visiter`a un terzo segmento R3 con secondo estremo il punto dove `
e presente lo specchio W2. Si ha che (R3)1+ = R1+ (Figura 3-4). Procediamo a definire N . Lo faremo per passi successivi.
(a) (b)
Figura 3-4: Sostituzione di R con M .
Primo passo. Definiamo N1. Poniamo uno specchio con orientamento corretto
nel punto ammissibile tra S1− e S e chiamiamo tale specchio Z1. Poniamo inoltre nel punto ammissibile tra S e S1+ uno specchio Z2 con orientamento opposto a quello di Z1. Otteniamo che la linea, dopo aver visitato S1−, passer`a a visitare un segmento interno alla regione che ci interessa. Chiamiamo tale segmento S1. Successivamente visiter`a un secondo segmento, S2, nel secondo estremo del quale poniamo uno specchio
Z3 con lo stesso orientamento di Z1. I segmenti S3 e S4
1 visitati successivamente saranno
quindi paralleli ad S (metteremo il pedice ad indicare il passo in cui uno specchio od un segmento vengono introdotti se pu`o succedere che ai passi successivi quello specchio o quel segmento vengano sostituiti o rimossi. Non lo metteremo se verranno solo rinominati.). Nel secondo estremo di S4
1 visitato dalla linea poniamo uno specchio Z14 con lo stesso
orientamento di Z2. Otteniamo che la linea visiter`a un segmento S15 al secondo estremo del quale poniamo uno specchio Z15 con lo stesso orientamento di Z1. La linea visiter`a poi un segmento S6 al secondo estremo del quale poniamo uno specchio Z6 con lo stesso orientamento di Z2. La linea visiter`a poi un segmento S7 al secondo estremo del quale
troviamo Z2. Poniamo N
1 = {S1, S2, S3, S14, S15, S6, S7} (Figura 3-5).
Ad ogni passo i successivo al primo, chiameremo Su
i il segmento privo di pedice
precedente al primo segmento con il pedice nella successione di Ni−1. Abbiamo quindi
Su
(a) (b)
Figura 3-5: Sostituzione di S con N : primo passo.
seguire con un percorso parallelo. Chiameremo tale segmento UiI. Poniamo U2I = S1+. Per sapere quanto sia lungo il percorso parallelo da seguire al passo i dovremo cercare un secondo segmento, UF
i , nel seguente modo. Abbiamo due possibilit`a.
1. Caso in cui si ha (aUiI, bUiI) = (aSui, bSui). Sia k
i il massimo intero positivo per cui
UiI, (UiI)1+, ..., (UiI)ki+ siano sulla stessa retta e non siano presenti autointersezioni
nei punti tra i segmenti considerati. Poniamo UF
i = (UiI)ki+.
2. Caso in cui si ha (aUI
i, bUiI) = (−aSui, −bSui). Sia ki il massimo intero positivo per cui
UI
i, (UiI)1−, ..., (UiI)ki
− siano sulla stessa retta e non siano presenti autointersezioni
nei punti tra i segmenti considerati. Poniamo UF
i = (UiI)ki−.
Nel primo dei due casi appena visti UI
i `e co-orientato con S, nel secondo non lo `e. Nel
seguito, per un segmento Q che si trova sul bordo della regione che ci interessa, useremo la notazione Q1+S per indicare il segmento successivo a Q se Q ed S sono co-orientati,
il precedente altrimenti. Controlliamo il motivo per cui UiF `e l’ultimo segmento della successione e avremo le informazioni per trovare Ui+1I . Dobbiamo controllare il secondo estremo VUiF di UF
i , quello su cui non `e incidente (UiI)(ki−1)+S. Possiamo avere i seguenti
casi.
1. In VUiF si trova uno specchio non corretto rispetto a (aSui, bSui). Poniamo UI
i+1 =
2. In VUF
i si trova uno specchio corretto rispetto a (aSiu, bSui). Se nel secondo estremo
di (UI
i)(ki+2)+S o di (UiI)(ki+3)+S troviamo W1 o W2 avremo che N = Ni e non
avremo bisogno di proseguire oltre. Altrimenti poniamo UI
i+1= (UiI)(ki+4)+S.
3. In VUF
i si trova lo specchio W1. Vedremo che N = Ni e non avremo bisogno di
proseguire oltre.
4. In VUiF si trova lo specchio W2. Vedremo che N = N
i e non avremo bisogno di
proseguire oltre.
5. In VUiF si trova un’autointersezione. Consideriamo l’unico segmento Q incidente
su VUF
i e diverso da UF
i che si trova sul bordo della regione che ci interessa. Se nel
secondo estremo di Q1+S o di Q2+S troviamo W1 o W2 avremo che N = N
i e non
avremo bisogno di proseguire oltre. Altrimenti poniamo UI
i+1= Q3+S.
Passo j-esimo. Se Zl
j−1 = W3 (o Zj−1l = W4 se R e S non erano stati presi
co-orientati) per un intero l, poniamo N = Nj−1. Altrimenti procediamo a definire
Nj. Lasciamo al loro posto gli specchi privi di pedice introdotti al passo precedente e
rimuoviamo quelli con il pedice. Per quanto riguarda i segmenti hanno il pedice tutti quelli che compaiono in Nj−1tra Sju(il segmento che termina incidendo sul primo specchio
con il pedice) e il primo segmento successivo a Sjuche incide su uno specchio senza pedice. Sia Nj−1− la successione Nj−1 privata dei segmenti con pedice. Vediamo come gestire i
vari casi.
1. Se in VUjF si trova uno specchio non corretto rispetto a (aSju, bSju) abbiamo UI
j+1=
(UI
j)(k+1)+S. Poniamo uno specchio (senza pedice) con lo stesso orientamento di
quello posto in VUjF al secondo estremo di (Su
j)(kj+3)+. Lasciamo proseguire con
(Sju)(kj+4)+e (Su
j)(kj+5)+ = Sj+1u , al secondo estremo del quale poniamo uno specchio
(con pedice) con orientamento opposto rispetto a quello posto in VUjF. Poniamo
un altro specchio con lo stesso orientamento di quello posto in VUjF (con pedice)
al secondo estremo di (Su
j)(kj+6)+ e uno con lo stesso orientamento (senza pedice)
al secondo estremo di (Su
j)(kj+7)+. A questo punto la linea prosegue e si chiude
passando per Z2 per costruzione. Poniamo quindi N
j = Nj−1− ∪ {(Sju)r+} con
r ∈ {1, ..., 2kj + 9} (Figura 3-6).
2. Se in VUjF si trova uno specchio corretto rispetto a (aS u j, bS
u
j) e se nel secondo estremo
di (UI
(a) (b)
Figura 3-6: Sostituzione di S con N : passo j−esimo, primo caso.
(Sju)kj+. Poniamo allora uno specchio con orientamento opposto rispetto a quello di
W3 (o W4) al secondo estremo di (Sju)(kj+1)+. Poniamo infine N
j = Nj−1− ∪{(Sju)r+}
con r ∈ {1, ..., 2kj+1}. Se nel secondo estremo di (UiI)(kj+3)+S troviamo W1 (o W2)
non avremo bisogno di definire UI
j+1, avremo N = Nj. Se nel secondo estremo di
(UI
i)(kj+2)+S e in quello di (UiI)(kj+3)+S non troviamo n´e W1n´e W2, abbiamo Uj+1I =
(UI
j)(kj+4)+S. Poniamo uno specchio (senza pedice) con lo stesso orientamento di
quello posto in VUjF al secondo estremo di (Su
j)(kj
−1)+. Poniamo uno specchio (con
pedice) con lo stesso orientamento di quello posto in VUjF al secondo estremo di
(Su
j)kj+ = Sj+1u . Poniamo uno specchio (con pedice) con orientamento opposto
rispetto a quello posto in VUjF al secondo estremo di (Su
j)(kj+1)+. Poniamo uno
specchio (senza pedice) con lo stesso orientamento di quello posto in VUjF al secondo
estremo di (Sju)(kj+3)+. Poniamo quindi N
j = Nj−1− ∪{(Sju)r+} con r ∈ {1, ..., 2kj+3}
(Figura 3-7). 3. Se in VUF
i si trova lo specchio W1 ponendo uno specchio con lo stesso orientamen-
to di W2 al secondo estremo di (Su
j)(kj+1)+ troviamo W3 al secondo estremo di
(Su
j)(kj+2)+. Poniamo quindi N = Nj = Nj−1− ∪ {(Sju)r+} con r ∈ {1, ..., 2kj+ 3}.
(a) (b)
(c) (d)
5. Se in VUjF si trova un’autointersezione dovremo effettuare gli stessi passi del caso
in cui ci sia uno specchio corretto rispetto a (aSju, bSju) dovendo solo fare attenzione
al fatto che UI
j+1 appartiene ad un ramo della linea diverso da quello dove si trova
UI j.
Il procedimento ovviamente avr`a termine dopo un numero finito di passi visto che l’interno della regione considerata possiede solo un numero finito di punti ammissibili. Inoltre si avr`a che M e N avranno uno spigolo in comune. Infatti N viene costruito parallelamente al bordo della regione considerata visitando tutti i punti ammissibili che distano meno di 2 dal bordo, proprio dove si trovano posti gli specchi W3 e W4, ed il
procedimento ha termine solo incontrando W3 o W4.
Per aggiungere un vertice al grafo Sona derivato da una linea di una curva di rifles- sione `e possibile dunque effettuare i seguenti passi. Per prima cosa occorre individuare la regione che ci interessa e i due rami co-orientati della linea da intersecare per aggiungere un vertice al grafo Sona derivato. Notiamo che i due rami possono coincidere. Dovre- mo preliminarmente controllare che nella frontiera della regione che ci interessa non ci siano spigoli dove tutti i segmenti ammissibili incidenti siano visitati dalla linea (4 per i punti interni e due per i punti sulle pareti, nel caso la regione che ci interessa sia quella esterna). Applichiamo la tecnica del ribaltamento degli spigoli nei punti dove questo accade. Applichiamo successivamente la tecnica di dilatazione della griglia con j = 7. Poi effettuiamo la procedura di avvicinamento di due segmenti scelti tra quelli possibili che si trovino ognuno su uno dei rami della linea scelti. Dopo aver eseguito la procedura di avvicinamento avremo che M e N , definiti come sopra, hanno uno spigolo in comune. Togliendo lo specchio presente in quello spigolo otteniamo l’intersezione voluta.
Abbiamo cos`ı la dimostrazione del teorema seguente.
Teorema 3.4. Ogni grafo gaussiano `e isomorfo ad un grafo Sona.