Next: Lezione 18
Up: Matematica Discreta (II modulo)
Previous: Lezione 16
Subsections
Definizione 17.1
Sia
![$ G$](img3.gif)
un grafo e sia
![$ v\in V(G)$](img1383.gif)
, chiameremo
grado di
![$ v$](img1216.gif)
il numero
(cardinale)
![$ \deg(v)=\left\vert\{e\in E(G) \mid v\in e\}\right\vert$](img1455.gif)
. Diremo che
![$ v$](img1216.gif)
ha
grado finito se
![$ \deg(v)\in \mathbb{N}$](img1456.gif)
.
Dimostrazione.
Siano
i vertici di
e
i suoi
lati. Per ogni
e
consideriamo il numero
Dalle proprietà associativa e commutativa della somma si ha evidentemente che
![$\displaystyle \sum_{i=1}^{n}\big(\sum_{j=1}^{k}m_{i,j}\big) = \sum_{j=1}^{k}\big(\sum_{i=1}^{n}m_{i,j}\big)$](img1462.gif) |
(10) |
Ma fissato
il numero
è uguale alla
cardinalità dell'insieme
che è uguale al numero dei lati che contengono
, ossia
. Pertanto il lato sinistro dell'uguaglianza
(10) è pari a
, ossia la somma dei gradi di
tutti i vertici.
Invece, fissato
, il numero
è pari alla
cardinalità dell'insieme
, che è uguale a
, dato
che ogni lato contiene esattamente due vertici. Ne consegue che il lato destro
della (10) è uguale a
.
Proposizione 17.3
In un grafo il numero di vertici di grado dispari è pari.
Proposizione 17.4
Se
![$ f$](img103.gif)
è un isomorfismo tra
![$ G$](img3.gif)
e
![$ G'$](img1219.gif)
e
![$ v\in V(G)$](img1383.gif)
allora
![$ \deg(v)=\deg(f(v))$](img1470.gif)
.
Definizione 17.5
Sia
![$ G$](img3.gif)
un grafo finito e sia
![$ V(G)=\{v_1,\dots,v_n\}$](img1471.gif)
, si chiama
score
di
![$ G$](img3.gif)
la successione (finita)
![$ n$](img2.gif)
-pla dei gradi dei suoi vertici ovvero
![$ \mathop{\rm score}\nolimits (G)=(\deg(v_1),\dots,\deg(v_n))$](img1472.gif)
.
Per scrivere lo score abbiamo dovuto ordinare i vertici del grafo e, ordinamenti
diversi producono
-ple diverse, ma che coincidono a meno di
riordinamento. Due score si considereranno quindi uguali se lo sono a meno di
riordinarli. Per comodità si ordineranno i vertici in modo che la successione
dei gradi sia non decrescente (i.e.
per ogni
).
Teorema 17.6
Se
![$ G$](img3.gif)
e
![$ G'$](img1219.gif)
sono grafi isomorfi, allora
![$ \mathop{\rm score}\nolimits (G)=\mathop{\rm score}\nolimits (G')$](img1474.gif)
.
Osservazione 17.7
Non è vero il viceversa del precedente teorema, si vedano ad esempio i grafi
i due grafi di figura
6 dell'esercizio
14.11.
Next: Lezione 18
Up: Matematica Discreta (II modulo)
Previous: Lezione 16
Domenico Luminati
2004-03-18