C ENNI ALLA TEORIA DEI GRAFI

D I E T I

DIPARTIMENTO DI I^NGEGNERIA E^{LETTRICA E DELLE} T^{ECNOLOGIE DELL}’INFORMAZIONE

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

C ENNI ALLA TEORIA DEI GRAFI

Ciro Visone

Definizioni ed applicazioni alla teoria dei circuiti

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Origini storiche della Teoria dei Grafi

A B

C

D e 1

e 2

e 3

e 4

e 5

e 6

e 7

Problema: E’ possibile raggiungere tutte le parti della città attraversando tutti i ponti una sola volta?

Tale percorso lo chiameremo Euleriano

Eulero trasforma la mappa in una struttura schematica che contiene tutte le proprietà di connessione tra le parti della terraferma e i ponti che le collegano: il GRAFO

A B

C

D e 1

e 2

e 3

e 4

e 5

e 6

e 7

I Ponti di Konisberg…

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Origini storiche della Teoria dei Grafi

A B

C

D e 1

e 2

e 3

e 4

e 5

e 6

e 7

Eulero conclude che il problema dei ponti di Konisberg non ammette soluzione!

Dato un GRAFO, è possibile individuare un percorso euleriano se e solo se il numero di vertici del grafo con ordine dispari non è superiore a due

Gli elementi A, B, C, D si definiscono VERTICI gli elementi e1, e2, … si definiscono LATI.

Il numero di lati che incidono in un vertice si definisce GRADO o ORDINE del vertice.

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

A B

C

D e 1

e 2

e 3

e 4

e 5

e 6

e 7

Un grafo è una struttura costituita da un insieme di vertici V, un insieme di lati E e da una relazione che esprime le connessioni tra di essi.

Definizione di GRAFO

Ben al di là dei destini delle passeggiate degli abitanti della cittadina tedesca, Eulero ci ha consegnato una teoria matematica che oggi trova largo uso in una gran quantità di applicazioni della fisica e dell’ingegneria.

Per esempio nella TEORIA DEI CIRCUITI ELETTRICI.

G = {V, E, ψ}

V = Insieme dei vertici, o nodi E = Insieme dei lati

= Relazione di incidenza

ψ

Esempio:

V = {A, B, C, D}

E = {e ¹ , e ₂ , . . . , e ₇ }

ψ(e

₁

) = AB ψ(e

₂

) = AC ψ(e

₃

) = AB ψ(e

₄

) = AC ψ(e

₅

) = AD ψ(e

₆

) = BD ψ(e

₇

) = CD

ψ : e ∈ E → V _a V _b ∈ V × V

Esempi e definizioni

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi e definizioni: Grafo e Sottografo

A B

C

D e 1

e 2

e 3

e 4

e 5

e 6

e 7

GRAFO

SOTTOGRAFO

G = {V, E, ψ}

H = {V′ , E′ , ψ}

V ≠ V′ ; E ≠ E′

V′ ⊆ V; E′ ⊆ E; ψ′ : E′ → V′ × V′

SOTTOGRAFO PROPRIO

ψ : e ∈ E → V _a V _b ∈ V × V

sottografo

sottografo proprio

sottografo proprio

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi e definizioni: Grafo Completo

GRAFO

GRAFO COMPLETO

G = {V, E, ψ}

∀V ₁ , V ₂ ∈ V(G), ∃e ∈ E(V) : ψ(e) = V ₁ V ₂ ψ : e ∈ E → V _a V _b ∈ V × V

Quadrilatero completo:

K

₄

Pentalatero completo:

K

₅

Per ogni coppia di nodi del grafo esiste un lato che li collega, o, più formalmente:

Trilatero completo:

K

₃

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi e definizioni: Grafo Bipartito

GRAFO BIPARTITO

G = {V, E, ψ}

Ogni lato del grafo unisce vertici appartenenti a partizioni X e Y diverse

V = X ∪ Y

∀e ∈ E, ψ(e) = ab ⇔ a ∈ X, b ∈ Y

GRAFO

G = {V, E, ψ}

ψ : e ∈ E → V _a V _b ∈ V × V

X

Y

X

Y

Grafo Bipartito Grafo Bipartito Completo

K

₄₂

Se risulta anche che:

∀a ∈ X, b ∈ Y ∃e ∈ E : ψ(e) = ab

allora il Grafo Bipartito si dice completo

Ogni coppia di nodi di due partizioni diverse è collegata da un lato!

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi e definizioni: Grado di connessione

GRAFO CONNESSO

Se il grafo è costituito da un’unica partizione, cioè , allora il grafo si dice CONNESSO.

ω = 1

V = ∪ V _k , k = 1,..,ω

Se ∀e ∈ E, ψ(e) = ab ⇔ a, b ∈ V _k

GRAFO

G = {V, E, ψ}

ψ : e ∈ E → V _a V _b ∈ V × V

Grafo non connesso:

ω = 3

risulta G = ∪ _k G(V _k )

Il Grafo è quindi PARTIZIONATO in parti

ω

X

Y Z

Grafo connesso:

ω = 1 PARTIZIONI DI UN GRAFO

Dato il grafo G, si considerino gli insiemi di nodi tali che:

V

₁

, . . . . , V

_ω

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi e definizioni: Matrice di Incidenza

Matrice di incidenza

3 where the symbol hi means the average over the can-

tilever’s length, while

⌘ = µ

₀

abN

2

41 +

µ_z

µ₀

1 1 +

_d

⇣

µz

µ₀

1 ⌘ (1

d

) 3

5 , (9)

⇠ = a⇣

_zz

n 1

_d

1 +

_d

⇣

µ_z

µ₀

1 ⌘ . (10)

where n is N/L. By using eqns. (4) and (8), the following expression for the average flux can be written:

h'i (t) = ⌘ (hH

^b

i + ni(t)) ⇠ L

I hm

⁰

i (t)

2

2

h 1 + 2 x

₀

i . (11) Finally, the circuit’s equation ' = Ri, in AC steady ˙ state condition, easily reads:

I = ˆ j!⇠

R + j!n⌘

L

I M ˆ

⁰

2

2

h 1 + 2 x

₀

i

, (12)

having assumed the bias field H

_b

as constant in time, while ˆ I and ˆ M

⁰

represent the phasors of the sinusoidal current i(t) and bending moment hm

⁰

i (t). It is easy to get that when a fully symmetric layout is concerned (the neutral axis lies exactly in the middle of the magneto- elastic layer, i.e. x

₀

= /2), no currents is induced and hence no output power is expected.

I. CHECK!!!

• aggiungere ipotesi di lavoro;

• controllare formule;

• scomporre formula potenza in modulo e fase e rap- presentare graficamente in funzione di R e !, al variare del parametro x

₀

;

• trovare relazione tra il momento flettente e la frec- cia, al fine di poter stimare tale grandezza e poter effettuare confronto misure/simulazioni (Damiano, ci pensi tu?)

2 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 5

a

_ij

=

8 >

<

> :

1 se e

_j

incide una volta nel vertice n

_i

, 0 se e

_j

non incide nel vertice n

_i

, 2 se e

_j

incide due volte nel vertice n

_i

1

2

3 4

e1 e2 e3

e4

e5

e6

e7

3 where the symbol hi means the average over the can-

tilever’s length, while

⌘ = µ

₀

abN

2

41 +

µ_z

µ₀

1 1 +

_d

⇣

µ_z

µ₀

1 ⌘ (1

d

) 3

5 , (9)

⇠ = a⇣

_zz

n 1

_d

1 +

_d

⇣

µ_z

µ₀

1 ⌘ . (10)

where n is N/L. By using eqns. (4) and (8), the following expression for the average flux can be written:

h'i (t) = ⌘ (hH

^b

i + ni(t)) ⇠ L

I hm

⁰

i (t)

2

2

h 1 + 2 x

₀

i . (11) Finally, the circuit’s equation ' = Ri, in AC steady ˙ state condition, easily reads:

I = ˆ j!⇠

R + j!n⌘

L

I M ˆ

⁰

2

2

h 1 + 2 x

₀

i

, (12)

having assumed the bias field H

_b

as constant in time, while ˆ I and ˆ M

⁰

represent the phasors of the sinusoidal current i(t) and bending moment hm

⁰

i (t). It is easy to get that when a fully symmetric layout is concerned (the neutral axis lies exactly in the middle of the magneto- elastic layer, i.e. x

₀

= /2), no currents is induced and hence no output power is expected.

I. CHECK!!!

• aggiungere ipotesi di lavoro;

• controllare formule;

• scomporre formula potenza in modulo e fase e rap- presentare graficamente in funzione di R e !, al variare del parametro x

₀

;

• trovare relazione tra il momento flettente e la frec- cia, al fine di poter stimare tale grandezza e poter effettuare confronto misure/simulazioni (Damiano, ci pensi tu?)

2 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 5

A =

2 6 4

1 0 0 0 1 1 0 1 1 1 2 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1

3 7 5

a

_ij

=

8 >

<

> :

1 se e

_j

incide una volta nel vertice n

_i

, 0 se e

_j

non incide nel vertice n

_i

, 2 se e

_j

incide due volte nel vertice n

_i

La somma degli elementi di ciascuna colonna è uguale a 2

La matrice di incidenza rappresenta in maniera sintetica la relazione di incidenza del grafo e contiene tutte le informazioni relative all’incidenza di un lato in un nodo.

Nella teoria dei circuiti avremo bisogno non solo di descrivere l’incidenza LATO-VERTICE ma anche se il lato è ENTRANTE o USCENTE dal NODO o vertice.

Tale richiesta può essere soddisfatta semplicemente orientando i lati del grafo, come vedremo più avanti.

Grado di un vertice: Numero di lati che incidono su quel nodo.

E’ facile verificare che il grado di un vertice è la somma degli elementi di una riga:

∑

k

a

_ik

= d(V

_i

)

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi e definizioni: Matrice di Incidenza

Matrice di incidenza

3 where the symbol hi means the average over the can-

tilever’s length, while

⌘ = µ

₀

abN

2

41 +

µ_z

µ₀

1 1 +

_d

⇣

µz

µ₀

1 ⌘ (1

d

) 3

5 , (9)

⇠ = a⇣

_zz

n 1

_d

1 +

_d

⇣

µ_z

µ₀

1 ⌘ . (10)

where n is N/L. By using eqns. (4) and (8), the following expression for the average flux can be written:

h'i (t) = ⌘ (hH

^b

i + ni(t)) ⇠ L

I hm

⁰

i (t)

2

2

h 1 + 2 x

₀

i . (11) Finally, the circuit’s equation ' = Ri, in AC steady ˙ state condition, easily reads:

I = ˆ j!⇠

R + j!n⌘

L

I M ˆ

⁰

2

2

h 1 + 2 x

₀

i

, (12)

having assumed the bias field H

_b

as constant in time, while ˆ I and ˆ M

⁰

represent the phasors of the sinusoidal current i(t) and bending moment hm

⁰

i (t). It is easy to get that when a fully symmetric layout is concerned (the neutral axis lies exactly in the middle of the magneto- elastic layer, i.e. x

₀

= /2), no currents is induced and hence no output power is expected.

I. CHECK!!!

• aggiungere ipotesi di lavoro;

• controllare formule;

• scomporre formula potenza in modulo e fase e rap- presentare graficamente in funzione di R e !, al variare del parametro x

₀

;

• trovare relazione tra il momento flettente e la frec- cia, al fine di poter stimare tale grandezza e poter effettuare confronto misure/simulazioni (Damiano, ci pensi tu?)

2 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 5

a

_ij

=

8 >

<

> :

1 se e

_j

incide una volta nel vertice n

_i

, 0 se e

_j

non incide nel vertice n

_i

, 2 se e

_j

incide due volte nel vertice n

_i

1

2

3 4

e1 e2 e3

e4

e5

e6

e7

3 where the symbol hi means the average over the can-

tilever’s length, while

⌘ = µ

₀

abN

2

41 +

µ_z

µ₀

1 1 +

_d

⇣

µ_z

µ₀

1 ⌘ (1

d

) 3

5 , (9)

⇠ = a⇣

_zz

n 1

_d

1 +

_d

⇣

µ_z

µ₀

1 ⌘ . (10)

where n is N/L. By using eqns. (4) and (8), the following expression for the average flux can be written:

h'i (t) = ⌘ (hH

^b

i + ni(t)) ⇠ L

I hm

⁰

i (t)

2

2

h 1 + 2 x

₀

i . (11) Finally, the circuit’s equation ' = Ri, in AC steady ˙ state condition, easily reads:

I = ˆ j!⇠

R + j!n⌘

L

I M ˆ

⁰

2

2

h 1 + 2 x

₀

i

, (12)

having assumed the bias field H

_b

as constant in time, while ˆ I and ˆ M

⁰

represent the phasors of the sinusoidal current i(t) and bending moment hm

⁰

i (t). It is easy to get that when a fully symmetric layout is concerned (the neutral axis lies exactly in the middle of the magneto- elastic layer, i.e. x

₀

= /2), no currents is induced and hence no output power is expected.

I. CHECK!!!

• aggiungere ipotesi di lavoro;

• controllare formule;

• scomporre formula potenza in modulo e fase e rap- presentare graficamente in funzione di R e !, al variare del parametro x

₀

;

• trovare relazione tra il momento flettente e la frec- cia, al fine di poter stimare tale grandezza e poter effettuare confronto misure/simulazioni (Damiano, ci pensi tu?)

2 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 5

A =

2 6 4

1 0 0 0 1 1 0 1 1 1 2 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1

3 7 5

a

_ij

=

8 >

<

> :

1 se e

_j

incide una volta nel vertice n

_i

, 0 se e

_j

non incide nel vertice n

_i

, 2 se e

_j

incide due volte nel vertice n

_i

La somma degli elementi di ciascuna colonna è uguale a 2

3 where the symbol hi means the average over the can-

tilever’s length, while

⌘ = µ ₀ abN

2

41 +

µ _z

µ ₀ 1 1 + _d ⇣

µ _z

µ ₀ 1 ⌘ (1 d )

3

5 , (9)

⇠ = a⇣ _zz n 1 _d 1 + _d ⇣

µ _z

µ ₀ 1 ⌘ . (10)

where n is N/L. By using eqns. (4) and (8), the following expression for the average flux can be written:

h'i (t) = ⌘ (hH ^b i + ni(t)) ⇠ L

I hm ⁰ i (t)

2

2

h 1 + 2 x ₀ i .

(11) Finally, the circuit’s equation ' = Ri, in AC steady ˙ state condition, easily reads:

I = ˆ j!⇠

R + j!n⌘

L

I M ˆ ⁰

2

2

h 1 + 2 x ₀ i

, (12)

having assumed the bias field H _b as constant in time, while ˆ I and ˆ M ⁰ represent the phasors of the sinusoidal current i(t) and bending moment hm ⁰ i (t). It is easy to get that when a fully symmetric layout is concerned (the neutral axis lies exactly in the middle of the magneto- elastic layer, i.e. x ₀ = /2), no currents is induced and hence no output power is expected.

I. CHECK!!!

• aggiungere ipotesi di lavoro;

• controllare formule;

• scomporre formula potenza in modulo e fase e rap- presentare graficamente in funzione di R e !, al variare del parametro x ₀ ;

• trovare relazione tra il momento flettente e la frec- cia, al fine di poter stimare tale grandezza e poter effettuare confronto misure/simulazioni (Damiano, ci pensi tu?)

A =?

2 6 4

a ₁₁ a ₁₂ . . . a _1n a ₂₁ a ₂₂ . . . a _2n . . . . a _n1 a _n2 . . . a _nn

3 7 5

A =

2 6 4

1 0 0 0 1 1 0 1 1 1 2 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1

3 7 5

a _ij =

8 >

<

> :

1 se e _j incide una volta nel vertice n _i , 0 se e _j non incide nel vertice n _i , 2 se e _j incide due volte nel vertice n _i

1

2

3

4

e1

e2

e3

e4

e5

e6

e7

e8

Trovare la matrice di incidenza del Grafo in figura.

ESERCIZIO

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi e definizioni: Grafo Planare

Grafo Planare

Grafo non Planare Un grafo è planare se può svilupparsi con qualunque deformazione

continua su un piano senza che i lati si intreccino.

Nell’esempio sopra il grafo è PLANARE, mentre quello in basso, se sviluppato in un piano, richiede comunque che il lato che connette i nodi A e B “incroci” necessariamente un lato del grafo.

ESERCIZIO

Un quadrilatero completo è planare?

Un pentagono completo è planare?

A A

B B

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi e definizioni: WALK, TRAIL e PATH

Cammino o WALK : sequenza di vertici e lati che unisce il vertice al vertice

V

₀

V

_k

1

2

3 4

e1 e2 e3

e4

e5

e6

e7

V

₀

e

₁

V

₁

e

₂

V

₂

. . . e

_k

V

_k

Tracciato o TRAIL: cammino senza ripetizioni di lati nella sequenza

Percorso o PATH : tracciato senza ripetizioni di vertici nella sequenza

CICLO O MAGLIA: E’ un tracciato senza ripetizioni di nodi interni. L’unica ripetizione di nodi ammessa è

V

₀

≡ V

_k

1e

₁

2e

₃

3e

₇

4e

₆

1

1e

₁

2e

₃

3e

₃

WALK 2e

₂

3e

₇

4

1e

₁

2e ^TRAIL

₃

3e

₂

2

4e PATH

₆

1e

₅

3e

₂

2

Lato percorso due volte

E’ una maglia!

Proprietà: Il grado di ogni nodo di una maglia è 2

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

Esempi di tagli:

T

₁

= e

₁

, e

₂

, e

₃

T

₂

= e

₁

, e

₅

, e

₇

1

2

3 4

e1 e2 e3

e4

e5

e6

e7

T ^AGLIO

TAGLIO: Insieme MINIMO di lati che asportati dal grafo ne aumenta l’ordine di connessione. In simboli:

T = {e

¹

, e

₂

, . . . , e

_r

} ⊆ E

G = {V, E, ψ}

^GRAFO

TAGLIO SE E SOLO SE

G* = {V, E − T, ψ}

^{TALE CHE}

ω(G*) > ω(G)

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T

^⇤

= {T e

_s

} with s = 1, .., r

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T = ˆ {T e

_s

} with s = 1, .., r

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T = ˆ {T e

_s

} with s = 1, .., r G = ˆ n

V, E T , ˆ o

Se, invece,

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T = ˆ {T e

_s

} with s = 1, .., r G = ˆ n

V, E T , ˆ o

!( ˆ G) = !(G)

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

T ^AGLIO

1

2

3 4

e1 e2 e3

e4

e5

e6

e7

taglio

1

2

3 4

e1 e2 e3

e4

e5

e6

e7

non è un taglio

TAGLIO: Insieme MINIMO di lati che asportati dal grafo ne aumenta l’ordine di connessione. In simboli:

T = {e

¹

, e

₂

, . . . , e

_r

} ⊆ E

G = {V, E, ψ}

^GRAFO

TAGLIO SE E SOLO SE

G* = {V, E − T, ψ}

^{TALE CHE}

ω(G*) > ω(G)

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T

^⇤

= {T e

_s

} with s = 1, .., r

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T = ˆ {T e

_s

} with s = 1, .., r

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T = ˆ {T e

_s

} with s = 1, .., r G = ˆ n

V, E T , ˆ o

Se, invece,

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T = ˆ {T e

_s

} with s = 1, .., r G = ˆ n

V, E T , ˆ o

!( ˆ G) = !(G)

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

CO -A ^LBERO

Se è un GRAFO e

un suo albero

G = {V, E, ψ}

è un co-albero

𝒜 E − L

(lati neri…)

A ^LBERO

𝒜 = {V, L, ψ}

GRAFO CONNESSO ALBERO: Grafo di cui ogni lato è un TAGLIO.

𝒜* = {V, L − e

^k

, ψ} : ω(𝒜*) > ω(𝒜) 𝒜 è un albero ⇕

∀e

_k

∈ L

(solo lati rossi…)

Albero

Path

Un albero non è necessariamente un path!

Dato un Grafo,

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T = ˆ {T e

_s

} with s = 1, .., r G = ˆ n

V, E T , ˆ o

!( ˆ G) = !(G) G(V, E, )

Un albero di un grafo è un sottografo

BRIEF ARTICLE 7

i(t) = J · nS R =

Z

⌘

ds

⌘S V = Ri

(E + E

^⇤

) = J E + E

^⇤

= 0 v

₀

=

Z

ext

E · tds =

Z

int

E · t

⁰

ds =

Z

int

E

_m

· t

⁰

ds =

Z

int

E

_m

· tds ⌘ "

v =

Z

int

E · t

⁰

ds =

I

int

E

_m

· tds

Z

int

1 J · tds Z

int

1 J · tds =

Z

int

1

S (J · tS)ds = Ri(t) v = " Ri

T = ˆ {T e

_s

} with s = 1, .., r G = ˆ n

V, E T , ˆ o

!( ˆ G) = !(G) G(V, E, ) A (V, L, )

di cui ogni lato è un TAGLIO.

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

G ^RAFI O ^{RIENTATI E} M ^ATRICI T ^OPOLOGICHE

Circuito: Su tutti i bipoli è stata assunta la convenzione dell’utilizzatore.

Assumendo pertanto il riferimento delle correnti, il riferimento per le tensioni è implicitamente assegnato!

Al circuito fisico associamo quindi un GRAFO ORIENTATO

1 2 3

4

e1 e2 e3

e4

e5

e6 e7

5

Per un GRAFO ORIENTATO la matrice di incidenza si definisce come segue:

BRIEF ARTICLE

THE AUTHOR

2 A =?

6 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 7 5

A = 2 6 6 6 6 4

1 0 0 0 0 1 0

0 1 0 0 0 0 1

0 0 1 0 0 1 1

1 1 0 1 1 0 0

0 0 1 1 1 0 0

3 7 7 7 7 5

a

_ij

=

8 >

<

> :

1 se e

_j

ENTRA nel vertice n

_i

, 0 se e

_j

NON INCIDE nel vertice n

_i

, + 1 se e

_j

ESCE dal vertice n

_i

1

MATRICE DI INCIDENZA +

-

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

G ^RAFI O ^{RIENTATI E} M ^ATRICI T ^OPOLOGICHE

Al circuito fisico associamo quindi un GRAFO ORIENTATO

1 2 3

4

e1 e2 e3

e4

e5

e6 e7

5

3 where the symbol hi means the average over the can-

tilever’s length, while

⌘ = µ

₀

abN

2

41 +

µ_z

µ₀

1

1 +

_d

⇣

µ_z

µ₀

1 ⌘ (1

d

) 3

5 , (9)

⇠ = a⇣

_zz

n 1

_d

1 +

_d

⇣

µ_z

µ₀

1 ⌘ . (10)

where n is N/L. By using eqns. (4) and (8), the following expression for the average flux can be written:

h'i (t) = ⌘ (hH

^b

i + ni(t)) ⇠ L

I hm

⁰

i (t)

2

2

h 1 + 2 x

₀

i . (11)

Finally, the circuit’s equation ' = Ri, in AC steady ˙ state condition, easily reads:

I = ˆ j!⇠

R + j!n⌘

L

I M ˆ

⁰

2

2

h 1 + 2 x

₀

i

, (12)

having assumed the bias field H

_b

as constant in time, while ˆ I and ˆ M

⁰

represent the phasors of the sinusoidal current i(t) and bending moment hm

⁰

i (t). It is easy to get that when a fully symmetric layout is concerned (the neutral axis lies exactly in the middle of the magneto- elastic layer, i.e. x

₀

= /2), no currents is induced and hence no output power is expected.

I. CHECK!!!

• aggiungere ipotesi di lavoro;

• controllare formule;

• scomporre formula potenza in modulo e fase e rap- presentare graficamente in funzione di R e !, al variare del parametro x

₀

;

• trovare relazione tra il momento flettente e la frec- cia, al fine di poter stimare tale grandezza e poter effettuare confronto misure/simulazioni (Damiano, ci pensi tu?)

A =?

2 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 5

A =

2 6 6 6 4

1 0 0 0 0 1 0

0 1 0 0 0 0 1

0 0 1 0 0 1 1

1 1 0 1 1 0 0

0 0 1 1 1 0 0

3 7 7 7 5

a

_ij

=

8 >

<

> :

1 se e

_j

ENTRA nel vertice n

_i

, 0 se e

_j

NON INCIDE nel vertice n

_i

, 2 se e

_j

ESCE dal vertice n

_i

Proprietà: La somma delle righe di una matrice di incidenza in un grafo orientato è ZERO!

Le righe della matrice di incidenza non sono INDIPENDENTI!

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

G ^RAFI O ^{RIENTATI E} M ^ATRICI T ^OPOLOGICHE

Circuito: Su tutti i bipoli è stata assunta la convenzione dell’utilizzatore.

A lato sono rappresentate alcune delle maglie orientate del grafo.

MATRICE DI MAGLIA

1 2 3

4

e1 e2 e3

e4

e5

e6 e7

5

m

₁

m

₂

m

₃

m

₄

m

₅

BRIEF ARTICLE

THE AUTHOR

2 A =?

6 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 7 5

A =

2 6 6 6 6 4

1 0 0 0 0 1 0

0 1 0 0 0 0 1

0 0 1 0 0 1 1

1 1 0 1 1 0 0

0 0 1 1 1 0 0

3 7 7 7 7 5

b

_ij

=

8 >

<

> :

1 se e

_j

2 m

ⁱ

– versi discordi

0 se e

_j

62 m

ⁱ

+ 1 se e

_j

2 m

ⁱ

– versi concordi

1

Anello

Ogni maglia di un GRAFO PLANARE che non contiene maglie al suo interno si definisce ANELLO

Nel grafo in figura

m

₁

, m

₂

, m

₃ sono degli anelli

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

G ^RAFI O ^{RIENTATI E} M ^ATRICI T ^OPOLOGICHE

Circuito: Su tutti i bipoli è stata assunta la convenzione dell’utilizzatore.

A lato sono rappresentate alcune delle maglie orientate del grafo.

ALCUNE MAGLIE SONO UNIONE DI ALTRE

m ₁ = e ₁ ∪ e ₂ ∪ e ₆ m ₂ = e ₂ ∪ e ₃ ∪ e ₇ m ₄ = m ₁ ∪ m ₂

I lati comuni si elidono!!!

E’ possibile individuare un insieme di maglie da cui costruire per unione tutte le altre del grafo.

Tali maglie si chiamano MAGLIE FONDAMENTALI

1 2 3

4

e1 e2 e3

e4

e5

e6 e7

5

m

₁

m

₂

m

₃

m

₄

m

₅

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

M ^AGLIE F ONDAMENTALI DI UN G ^RAFO

MAGLIA FONDAMENTALE

BRIEF ARTICLE

THE AUTHOR

2 A =?

6 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 7 5

A =

2 6 6 6 6 4

1 0 0 0 0 1 0

0 1 0 0 0 0 1

0 0 1 0 0 1 1

1 1 0 1 1 0 0

0 0 1 1 1 0 0

3 7 7 7 7 5

b

_ij

=

8 >

<

> :

1 se e

_j

2 m

ⁱ

– versi discordi

0 se e

_j

62 m

ⁱ

+ 1 se e

_j

2 m

ⁱ

– versi concordi

1

ALBERO Aggiungendo all’albero un lato di co-albero viene chiusa

una maglia, che si definisce MAGLIA FONDAMENTALE.

Il Numero di maglie fondamentali è pari al numero di lati di co-albero

l − (n − 1)

La definizione degli elementi della matrice NON CAMBIA!

Ogni altra maglia è ottenibile come unione di maglie fondamentali

m

₁

m

₂

m

₄

m

₃

m

₅

m

₂

e1

e2

e3

e4

e5

e6 e7

m

₁

m

₂

m

₃

m

₄

= m

₁

∪ m

₂

m

₅

= m

₂

∪ m

₃

m

₆

= m

₁

∪ m

₂

∪ m

₃

m

₆

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

T ^AGLI F ONDAMENTALI DI UN G ^RAFO

MATRICE DI TAGLIO FONDAMENTALE

Si può mostrare che per ogni lato di albero è possibile costruire un taglio che lo contenga.

Esso viene definito come TAGLIO FONDAMENTALE.

Il Numero di tagli fondamentali è pari al numero di lati di albero:

(n − 1)

BRIEF ARTICLE

THE AUTHOR

2 A =?

6 6 4

a

₁₁

a

₁₂

. . . a

_1n

a

₂₁

a

₂₂

. . . a

_2n

. . . . a

_n1

a

_n2

. . . a

_nn

3 7 7 5

A =

2 6 6 6 6 4

1 0 0 0 0 1 0

0 1 0 0 0 0 1

0 0 1 0 0 1 1

1 1 0 1 1 0 0

0 0 1 1 1 0 0

3 7 7 7 7 5

⌧

_ij

=

8 >

<

> :

1 se e

_j

entra in S

_i

0 se e

_j

non incide in S

_i

+ 1 se e

_j

esce da S

_i

1

𝒯

₁

𝒯

₂

𝒯

₃

1 2

3 4

e

₁

e

₂

e

₃

e

₄

e

₅

e

₆

𝒯

₁

𝒯

₂

1 0 0 0 0 1 0 1 0 -1 1 1

𝒯

₃

0 0 -1 1 -1 0

-1 1 0 -1 1 0 1

0 0 -1 1 -1 0 ² 1 0 0 0 0 1 ³

Nel grafo si può vedere c h e a l c u n i t a g l i coincidono con i lati che incidono in un nodo, mentre ad esempio il taglio si ottiene come unione dei lati dei nodi 1 e 3.

In altri termini, le righe della Matrice di Taglio s o n o c o m b i n a z i o n i lineari delle righe di .

𝒯

₂

A

_r

Le righe della matrice di taglio fondamentale sono INDIPENDENTI.

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

E ^{QUIVALENZA TRA LE EQUAZIONI AI NODI E LE EQUAZIONI AGLI INSIEMI DI TAGLIO}

Se consideriamo un insieme di taglio esso divide il grafo in due parti disgiunte.

e sono i due sottografi disgiunti e il primo contiene i primi m nodi. Essi corrispondono a m righe della matrice. Sommando tali righe, solo gli elementi che corrispondono ai lati dell’insieme di taglio non si elidono (gli altri lati appartengono a ).

8 THE AUTHOR

v = d

dt = µ

₀

N

²

⇡a

²

h

di dt T

_k

8 THE AUTHOR

v = d

dt = µ ₀ N ² ⇡a ² h

di dt T _k

8 THE AUTHOR

v = d

dt = µ ₀ N ² ⇡a ² h

di dt T _k

G ₁

8 THE AUTHOR

v = d

dt = µ

₀

N

²

⇡a

²

h

di dt T

_k

G

₂

m nodi

n-m nodi

8 THE AUTHOR

v = d

dt = µ

₀

N

²

⇡a

²

h

di dt T

_k

G

₁

8 THE AUTHOR

v = d

dt = µ ₀ N ² ⇡a ² h

di dt T _k

G ₂

i

r

i

s

i

p

8 THE AUTHOR

v = d

dt = µ

₀

N

²

⇡a

²

h

di dt T

_k

G

₂

X

m

k=1

a

_kj

i

_j

⌘ i

^r

+ i

_s

i

_p

= 0

8 THE AUTHOR

v = d

dt = µ

₀

N

²

⇡a

²

h

di dt T

_k

G

₁

In conclusione ogni LK agli insiemi di taglio si ottiene da una c.l. di equazioni ai nodi. Vale anche il viceversa.

Le righe della matrice di taglio sono c.l. della matrice di incidenza ridotta e viceversa.

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

F ^{ORMA SINTETICA DELLE EQUAZIONI DI} K ^IRCHHOFF

Le equazioni di Kirchhoff alle correnti possono scriversi come segue:

𝒜 i = 0

Dal momento che la matrice non ha rango pieno, è possibile considerare la matrice di incidenza ridotta, ottenuta eliminando una riga della matrice di incidenza.

𝒜

𝒜 _r i = 0

Ma la matrice

𝒜

_r ha rango pieno?

Le righe di sono combinazioni lineari di ;

Ogni riga di ha un elemento diverso da zero non condiviso con le altre righe, cioè le righe di sono LINEARMENTE INDIPENDENTI;

Pertanto anche la matrice ha rango pieno.

𝒯 𝒜

_r

𝒯 𝒯

𝒜

_r

𝒯i = 0

Legge di Kirchhoff alle correnti - LKC

Rappresenta equazioni alle correnti linearmente indipendenti.

n − 1

Possiamo concludere che il numero massimo di LKC L.I. è

n − 1

Possiamo formulare quindi, come usuale, le LKC attraverso la matrice di incidenza ridotta.

In altri termini, per formulare le LKC basterà scrivere le equazioni alle correnti per

n − 1

nodi della rete.

Fondamenti di Circuiti Elettrici Ingegneria Informatica e Automatica

Ciro Visone — Teoria dei Grafi

F ^{ORMA SINTETICA DELLE EQUAZIONI DI} K ^IRCHHOFF

Le equazioni di Kirchhoff alle tensioni possono scriversi come segue:

ℬ v = 0

Con intendiamo la MATRICE DI MAGLIA FONDAMENTALE.

ℬ

Ma la matrice ha rango pieno?

ℬ

Ogni riga di ha un elemento diverso da zero non condiviso con le altre righe, perché corrisponde al lato di co-albero che ha in esclusiva;

Quindi le righe di sono LINEARMENTE INDIPENDENTI;

Pertanto la matrice ha rango pieno.

ℬ

ℬ ℬ

Poiché ogni altra maglia è unione di maglie fondamentali

ogni altra equazione alla maglia è una C.L. delle equazioni alle maglie fondamentali

Pertanto, possiamo concludere che il numero massimo di LKT L.I. è

l − (n − 1)

Si potrebbe dimostrare che in un grafo planare il numero di anelli è pari a

l − (n − 1)

In un grafo planare le LKT possono scriversi per gli

l − (n − 1)

ANELLI DEL GRAFO!