Newsgroup: it.hobby.enigmi
Titolo: Grafo

      *---------*
      |         |
      |         |
      |         |
      *---------*
Questo grafo ha le due proprieta' seguenti:
1) Se due vertici sono connessi, non hanno punti vicini in comune.
2) Se due vertici non sono connessi, hanno esattamente due punti vicini in 
comune.
Per punti vicini, intendo direttamente collegati da un arco.
Trovare un grafo con piu' di 4 vertici che rispetta le due suddette proprieta'.
:) dario

 proprieta'.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8 vertici, 13 archi:
           A - - - - - B
         / |           | \
       /   |           |   \
     /     C_ _        |     \
   /       | \  - - _ _|       \
 /         |   \       |- - _ _  \
G _ _      |     \     |        - H
 \    - - _|_      \   |         /
   \       |  - - _ _\ |       /
     \     |          -D     /
       \   |           |   /
         \ |           | /
           E - - - - - F
La condizione 2) implica che ogni coppia di vertici non direttamente
connessi si trova ai vertici opposti di un quadrilatero.
Anche: tra ogni coppia di punti del grafo esiste un percorso di al più due
archi, ed il numero di percorsi distinti è pari alla loro lunghezza, volendo
generalizzare a (iper)"cubi" l'esempio di partenza.
Quello riportato è stato fatto ad occhio a partire dai quadrilateri ABCD e
CDEF, imponendo alle coppie AE e BF il trovarsi a vertici opposti di un
quadrilatero (ACEG e BDFH) ed infine imponendo la raggiungibilità in due
passi di ogni nodo del grafo a partire da C (DG) ed infine per simmetria su
D (CH).
Avevo cominciato a farlo algebricamente con condizioni sulla matrice di
adiacenza... qualcuno l'ha già fatto, vero? :)
Buone feste
Stefano

 Stefano
Altrettanto da parte mia.
dario

 nell'esposto, 3 punti in comune, BCF (ADE)
wow che abbaglio ho preso!!!
ciao

Ci riprovo ^__^;;;
La prima condizione può essere espressa come: "non ci sono triangoli nel
grafo" (sottografi di ordine 3 completamente connessi).
[se fosse presente una terna di punti ABC, i punti A e B, connessi avrebbero
almeno il punto C vicino in comune]
La seconda condizione può essere espressa come: "ogni coppia di vertici non
direttamente connessi si trova ai vertici opposti di un quadrilatero".
[per costruzione]
In termini di matrice d'adiacenza:
La prima condizione: "dove la matrice A è non nulla (e vale 1), la A*A lo è
(non ci sono percorsi di lunghezza due che connettano i nodi)".
La seconda condizione: "dove la matrice A è nulla, la A*A vale esattamente 2
(ci sono due percorsi di lunghezza 2 tra i nodi)".
Quindi il problema si potrebbe affrontare a forza bruta cercando matrici di
adiacenza per le quali 2*A+A*A ha tutti gli elementi pari a 2. Ma già per un
grafo di otto nodi questo richiede 2^28 tentativi (cioè almeno un prodotto
scalare di dimensione 8).
Adesso sono piuttosto convinto che non esista un grafo di ordine maggiore di
quattro che soddisfi le condizioni date. Sarà un altro abbaglio.
Parto da un grafo con due nodi: 
a) non sono connessi: allora per la 2a cond. devo aggiungere due punti e
quattro archi (e arrivo al quadrato)
b) sono connessi: allora tutto ok, ma i nodi non sono più di 4, quindi si
deve aggiungere almeno un nodo
b1) non connesso a nessuno dei precedenti: viola la 2a condizione (non sono
ammissibili nodi isolati)
b2) connesso ad entrambi: è un triangolo, viola la 1a condizione.
b3) connesso solo ad uno: per soddisfare la 2a condizione devo aggiungere 1
nodo e due archi (e di nuovo arrivo al quadrato)
Continuo allora (a e b3) da un grafo quadrilatero, aggiungendo un nodo non
isolato. Poiché nel grafo non debbono esservi triangoli, non posso
aggiungere altri archi. E la condizione 2 non può essere verificata.
Quindi devo aggiungere un altro nodo (finora 6) connesso al penultimo
aggiunto (un po' a mo di carro dell'orsa). Quest'ultimo può essere connesso
ad uno degli angoli a distanza 3 oppure all'angolo a distanza 4.
a) angolo a distanza 3: due quadrati connessi per un lato.
b) angolo a distanza 4: affinchè la condizione 2 sia verificata è necessario
chiudere un triangolo.
L'unica foglia ancora possibile è quella dei due quadrilateri connessi per
un lato. Chiamati i due ABCD e CDEF come in precedenza, devo aggiungere i
due nodi G ed H affinchè sia verificata la 2a condizione.
           A - - - - - B
         / |           | \
       /   |           |   \
     /     |           |     \
   /       |           |       \
 /         |           |         \
G          C - - - - - D          H
 \         |           |         /
   \       |           |       /
     \     |           |     /
       \   |           |   /
         \ |           | /
           E - - - - - F
E a questo punto non è possibile aggiungere archi al fine di non violare la
2a condizione senza violare la prima.
Dove mi sbaglio?
Stefano

 Ci riprovo ^__^;;;
Esistono almeno 2 soluzioni.
La piu' piccola richiede 16 vertici.
ciao :) dario

 La piu' piccola richiede 16 vertici.
Con l'aiuto di quest'ultima informazione, ho trovato, salvo errori, una
soluzione:
.  a0 b0 c0 d0 a1 a2 a3 b1 b2 b3 c1 c2 c3 d1 d2 d3
a0  .  x  0  x  x  x  x  0  0  0  0  0  0  0  0  0
b0  x  .  x  0  0  0  0  x  x  x  0  0  0  0  0  0
c0  0  x  .  x  0  0  0  0  0  0  x  x  x  0  0  0
d0  x  0  x  .  0  0  0  0  0  0  0  0  0  x  x  x
a1  x  0  0  0  .  0  0  x  0  0  0  x  x  x  0  0
a2  x  0  0  0  0  .  0  0  x  0  x  0  x  0  x  0
a3  x  0  0  0  0  0  .  0  0  x  x  x  0  0  0  x
b1  0  x  0  0  x  0  0  .  0  0  x  0  0  0  x  x
b2  0  x  0  0  0  x  0  0  .  0  0  x  0  x  0  x
b3  0  x  0  0  0  0  x  0  0  .  0  0  x  x  x  0
c1  0  0  x  0  0  x  x  x  0  0  .  0  0  x  0  0
c2  0  0  x  0  x  0  x  0  x  0  0  .  0  0  x  0
c3  0  0  x  0  x  x  0  0  0  x  0  0  .  0  0  x
d1  0  0  0  x  x  0  0  0  x  x  x  0  0  .  0  0
d2  0  0  0  x  0  x  0  x  0  x  0  x  0  0  .  0
d3  0  0  0  x  0  0  x  x  x  0  0  0  x  0  0  .
a0..a3..d0..d3 sono i 16 vertici; le x indicano le connessioni; da ogni
vertice partono 5 archi, 40 archi in tutto (nello schema ovviamente il
numero di X è raddoppiato)
la costruzione geometrica:
parto da un quadrato A0,B0,C0,D0
da ciascun vertice escono tre archi: A0-A1; A0-A2; A0-A3, B0-B1 ecc.
. A2  A3         B1  B2
.  \  |          |  /
.   \ |          | /
A1   \|          |/     B3
.----------------------
.     |A0      B0|
.     |          |
.     |          |
D3    |D0      C0|     C1
.----------------------
.    /|          |\
.   / |          | \
.D2/  |D1      C3|  \C2
connetto le estremità di questi archi come segue:
lettere *adiacenti* e numeri uguali (e formo altri tre quadrati A1,B1,C1,D1;
A2,B2,C2,D2; A3,B3,C3,D3)
e finisco connettendo lettere *opposte* e numeri diversi:
A1-C2; A1-C3;   A2-C1; A2-C3.....B3-D1; B3-D2
ciao
paolo

 d3  0  0  0  x  0  0  x  x  x  0  0  0  x  0  0  .
wow!!!
come hai fatto? geometricamente?
un dio!
Astonished Stefano
(2*A+A*A==2 ovunque tranne che sulla diagonale==5 percorsi che tornano
indietro al punto di partenza qualunque esso sia)

 
Ottimo Paolo,
Mi sembra che vada bene.
E' possibile disegnarlo o meglio immaginarlo cosi',  prendere la proiezione 
tridimensionale di un tesseratto. Sono 2 cubi, il piu' piccolo e' centrato 
rispetto al piu' grande ed ogni vertice di quello interno e' collegato con 
il vertice piu' vicino del cubo grande. A questo punto basta aggiungere le 
otto diagonali spaziali. Si ottengono, difatti 40 archi.
ciao dario

"Dario Uri" ha scritto

Forse c'è un metodo più semplice per descrivere (non per disegnare) il
grafo:
partendo dal mio quadrato iniziale, cambio le etichette con una doppia
riflessione (A0 diventa C0 e vv; B0 diventa D0 e vv.)
Allora inizio disegnando quattro quadrati
A0,B0,C0,D0
A1,B1,C1,D1
A2,B2,C2,D2
A3,B3,C3,D3
ora basta collegare tutte le coppie di vertici con lettera opposta (A-C
oppure B-D) e cifra differente
A0-C1, A0-C2, A0-C3
A1-C0, A1-C2, A1-C3
ecc.
ancora più semplice
numero i sedici vertici in base quattro
00,01,02,03,10,11,12,13,20,21,22,23,30,31,32,33
e connetto le coppie di vertici secondo due criteri
_seconda cifra uguale e prima cifra con diversa parità, e ottengo i quattro
quadrati:
00,10,20,30,00
01,11,21,31,01
02,12,22,32,02
03,13,23,33,03
__seconda cifra diversa e prima cifra con uguale parità:
00-21; 00-22; 00-23
10-31; 10-32; 10-33
ecc.
____________
sono curioso di conoscere l'altra soluzione
ciao
paolo

 sono curioso di conoscere l'altra soluzione
Il grafo da te descritto e' noto col nome di Clebsch, la seconda soluzione 
e' il grafo di Gewirtz (56 vertici di valenza 10) entrambi fanno parte di 
una famiglia di grafi estremamente regolari: "Strongly Regular Graphs".
Per la prima soluzione (16,5) ho trovato un disegno qua:
http://www.pbase.com/image/12542
.
ciao dario