1 Numero di cammini in un grafo

Enumerazione di cammini e di cicli in un grafo

Fabrizio Pugliese

Abstract

Come applicazione della matrice d’adiacenza, ricaviamo alcune formule per il calcolo del numero di cammini e cicli di lunghezza fissata.

1 Numero di cammini in un grafo

Sia G = (V, E) un grafo (semplice non orientato) con n vertici v

, . . . , v

ed m lati, e sia A : F → F il suo operatore d’adiacenza, definito da

A(f )(v)

= X

z∼v

f (z),

per ogni v ∈ V e per ogni funzione f : V → R; sia A(G) = ka

(G)k

la matrice d’adiacenza, cio`e la matrice di A rispetto alla base di F formata dalle funzioni caratteristiche χ

, . . . , χ

dei vertici, cio`e

a

(G) = a

(G) = A(G)(χ

)(v

)

Ricordiamo che il numero di passeggiate di lunghezza k dal vertice v

al vertice v

`e

w

(G) = a

(G), dove

A

(G)

= A(G) · A(G) · · · A(G) =

° °

°a

(G)

° °

°

i,j=1

Vogliamo descrivere un ”algoritmo” per calcolare il numero

p

(G) = numero di k-cammini in G fra i vertici v

e v

A questo scopo denotiamo, per ogni grafo G, per ogni A, B ⊂ V (G) e per ogni k ∈ N, con S

(G) l’insieme dei k-cammini in G con vertice iniziale in A e vertice finale in B. Siano, inoltre, per ogni W ⊂ V (G),

N

(G) = {vertici di V

\W adiacenti a W } , E

(G) = {lati di E

incidenti con W } ,

e sia

G

= G\E

= (V (G), E(G)\E

)

il grafo ottenuto da G sconnettendo tutti i vertici di W (che quindi, in G

,

`e un insieme di vertici isolati). E’ facile capire che, dati due vertici distinti v, w ∈ V (G), l’insieme S

(G), con k ≥ 2, `e in corrispondenza biunivoca con l’insieme S

w(G)\{v}

(G

) (la corrispondenza `e quella che associa ad ogni k- cammino da v a w il sottocammino formato dai primi k − 1 lati); d’altra parte

`e anche chiaro che S

w(G)\{v}

(G

) = [

z∈Nw(G)\{v}

S

(G

),

con gli addendi a secondo membro a due a due disgiunti; quindi

¯ ¯S

(G) ¯

¯ = ¯

¯ ¯S

w(G)\{v}

(G

)

¯ ¯

¯ = X

v6=z∈Nw(G)

¯ ¯S

(G

) ¯

¯ ,

cio`e (denotando G

semplicemente con G

),

p

(G) = X

a

(G) p

(G

); (1)

si noti, in particolare, che

p

(G) = 0, per ogni k ∈ N, i ∈ {1, . . . , n}.

Dunque: per calcolare tramite la (1) il numero di k-cammini da v

a v

nel grafo G devo prima calcolare quanti (k −1)-cammini ci sono, nel grafo G

, fra v

e ciascun vertice adiacente a v

nel grafo G. Riapplicando il procedimento a G

mi riduco a calcolare dei p

(G

) con i v

adiacenti a v

in G

e G

= (G

)

ottenuto da G sconnettendo v

e v

(si noti che G

= G

); ecc...

Naturalmente, ad ogni passo di questo algoritmo ricorsivo il numero di p

(G

) da calcolare cresce, a volte anche ”esponenzialmente”, ma d’altra parte i grafi G

diventano sempre pi` u semplici a mano a mano che sconnet- tiamo vertici da G.

Sarebbe bello poter trovare delle formule esplicite per i p

(G) in funzione della matrice d’adiacenza A(G) e delle sue potenze. Purtroppo non `e semplice farlo se k non `e basso, comunque facciamo qualche calcolo per k = 2, 3, 4 . . . . Evidentemente, vale

p

(G) = a

(G), (2)

passiamo a k = 2. Applicando (1) si ha

p

(G) = X

a

(G)p

(G

);

ma, per la (2) applicata al caso G = G

, si ha

p

(G

) = a

(G

) = (1 − δ

) (1 − δ

) a

(G), (3)

e sostituendo nell’espressione precedente si ottiene p

(G) = (1 − δ

) X

r

(1 − δ

) a

(G)a

(G)

= (1 − δ

) (

a

− X

r

a

(G)δ

a

(G) )

,

cio`e, tenendo conto che a

(G) = 0,

p

(G) = (1 − δ

) a

(G), (4) come c’era da aspettarsi (una 2-passeggiata fra vertici distinti `e ovviamente un 2-cammino).

Passiamo a k = 3. Sempre applicando la (1) e tenendo conto di (4) si ottiene

p

(G) = X

a

(G)p

(G

), (5)

con p

(G

) data dalla (4) sostituendo G con G

: p

(G

) = (1 − δ

) a

(G

) ; dobbiamo valutare gli elementi di A

(G

), sfruttando (3):

a

(G

) = X

a

(G

)a

(G

)

= (1 − δ

) (1 − δ

) X

s

(1 − δ

) a

(G)a

(G) (6)

= (1 − δ

) (1 − δ

)

³

a

(G) − a

(G)a

(G)

´

(si osservi che (1 − δ

)

= 1 − δ

); quindi, p

(G

) = (1 − δ

) (1 − δ

) (1 − δ

) ³

a

(G) − a

(G)a

(G) ´

(7) sostituendo nella (5) otteniamo:

p

(G) = (1 − δ

) X

(1 − δ

) (1 − δ

) a

(G) n

a

(G) − a

(G)a

(G) o

che con semplici passaggi (in cui si sfrutta il fatto che a

= 0, che a

= a

e che P

r

a

`e uguale al grado d

del vertice v

) diventa p

(G) = (1 − δ

) n

a

(G) − a

(G)(d

(G) + d

(G) − 1) o

(8)

Studiamo il caso k = 4. Sempre applicando la (1) si ha p

(G) = X

r

a

(G)p

(G

); (9)

d’altra parte, per la (8) vale p

(G

) = (1 − δ

) n

a

(G

) − a

(G

)(d

(G

) + d

(G

) − 1) o

, (10) con

d

(G) = a

grado del vertice v

nel grafo G; evidentemente vale

d

(G

) = (1 − δ

) (d

(G) − a

(G)) ; (11) a

(G

) `e dato dalla (3), resta da calcolare la matrice A

(G

):

a

(G

) = X

s

a

(G

)a

(G

)

= (1 − δ

) (1 − δ

) X

s

(1 − δ

) a

(G) n

a

(G) − a

(G)a

(G) o

,

cio`e, in definitiva,

a

(G

) = (1 − δ

) (1 − δ

) n

a

(G) − a

(G)a

(G) − a

(G)a

(G) o

(12) Sostituendo (11) e (12) in (10) si ottiene

p

(G

) = (1 − δ

) (1 − δ

) (1 − δ

) n

a

− a

a

− a

a

− a

(d

+ d

− a

− a

− 1) o (13)

Sostituendo in (9) si ottiene

p

= (1 − δ

) (

a

− a

(d

+ d

− 3a

− 2) − a

³

a

+ a

´

− X

r

d

a

a

)

1Spesso, nel seguito di questo appunto, ometteremo la specificazione ”da 1 a n” nelle sommatoie con tale range e la specificazione ”(G)” per le grandezze relative a tale grafo

2 Numero dei cicli in un grafo.

Per ogni intero k, denotiamo con C

il numero di k-cicli passanti per il vertice v

e con C

(G) il numero totale di k-cicli nel grafo; evidentemente,

C

(G) = 1 k

X

C

(14)

Per calcolare C

possiamo utilizzare la formula

C

= 1 2

X

i,r

(1 − δ

) a

a

p

(G

) ; (15)

infatti, un k-ciclo passante per v

`e individuato da due vertici v

, v

adiacenti a v

e da un (k − 2)-cammino da v

a v

non passante per v

(il fattore 1/2 deriva dal fatto che scambiando v

con v

il k-ciclo non cambia). Notiamo che, combinando (14) con (15) e con (1), si ottiene

C

(G) = 1 2k

X

i,j

a

p

= 1

2k T r (AP

) ,

che si sarebbe potuta ricavare direttamente considerando che: 1) ogni k-ciclo passante per il lato v

v

`e la somma di tale lato con un (k − 1)-cammino da v

a v

; 2) sommando il numero di cicli di cui al punto 1) su tutte le coppie ordinate (v

, v

) tali che v

∼ v

, ogni ciclo risulta contato 2k volte (perch`e contiene k lati e pu`o essere percorso in due versi distinti).

Tornando alle formule (14), (15), consideriamo il caso pi` u semplice, k = 3;

per la (14), il numero di triangoli nel grafo G `e:

C

(G) = 1 3

X

C

;

d’altra parte, applicando (15) si ha C

= 1

2 X

i,r

(1 − δ

) a

a

p

(G

) ,

che, ricordando (3), ci fornisce il numero dei triangoli passanti per v

: C

= 1

2 X

i,r

(1 − δ

) (1 − δ

) (1 − δ

) a

a

a

= 1 2

X

i,r

a

a

a

= 1

2 a

;

dunque, il numero totale di triangoli in G `e C

(G) = 1

6 T rA

Consideriamo il caso k = 4; la (15) diventa

C

= X

i,r

(1 − δ

) a

a

p

(G

); (16)

ora, applicando la (4) al grafo G

e tenendo conto di (6), si ottiene p

(G

) = (1 − δ

) (1 − δ

) (1 − δ

) n

a

− a

a

o

che sostituita in (16) ci d`a C

= 1

2 X

i,r

(1 − δ

) (1 − δ

) (1 − δ

) a

a

n

a

− a

a

o

; (17)

ora, il prodotto dei primi tre fattori `e della forma (1 − δ

+ termini contenenti δ

o δ

), e questi ultimi termini non contano perch`e vanno moltiplicati per a

a

, che si

annulla quando i = j oppure r = j; dunque la (17) si riduce a C

= 1

2 X

i,r

(1 − δ

) a

a

n

a

− a

a

o

= 1 2

(

a

− d

− X

i

a

d

+ d

)

;

ma allora la (14) diventa

C

(G) = 1 4

X

j

C

= 1 8

 

 T rA

− 2 X

j

d

+ 2 X

j

d

 



= 1 8 T r

n

A

− 2 b d

+ b d o

,

essendo b d = kd

δ

k l”operatore diagonale associato alla funzione grado d.

Consideriamo ora il caso k = 5, i calcoli sono analoghi ai precedenti, solo un

po’ pi` u lunghi... Il numero di 5-cicli passanti per il vertice v

`e C

= 1

2 X

i,r

(1 − δ

) a

a

p

(G

)

= 1 2

X

i,r

(1 − δ

) (1 − δ

) (1 − δ

) a

a

n

a

− a

a

− a

a

− a

(d

+ d

− a

− a

− 1) o

= 1 2

X

i,r

(1 − δ

− δ

− δ

+ · · · − δ

δ

δ

) a

a

n

a

− a

a

− a

a

− a

(d

+ d

− a

− a

− 1) o

= 1 2

X

i,r

(1 − δ

) a

a

n

a

− a

a

− a

a

− a

(d

+ d

− a

− a

− 1) o

;

nell’ultimo passaggio si `e sfruttato il fatto che, quando i = j oppure r = j, il fattore a

a

si annulla; quindi, nello sviluppo della sommatoria a penultimo membro, si annullano tutte le ”sottosommatorie” contenenti i fattori δ

o δ

; sviluppando l’ultimo membro si ottiene

C

= 1 2

(

a

− 2a

d

− 2 X

i

d

a

a

+ 5a

− X

i

a

a

)

;

applicando la (14) per k = 5 otteniamo il numero totale di 5-cicli in G:

C

(G) = 1 10



T rA

+ 5T rA

− 5 X

j

d

a





= 1 10 T r ³

A

+ 5A

− 5 b dA ´