Next: Lezione 18 (16 maggio
Up: Matematica Discreta
Previous: Lezione 16 (9 maggio
Subsections
Definizione 17.1
Sia
![$G$](img3.gif)
un grafo e sia
![$v\in V(G)$](img1284.gif)
, chiameremo
grado di
![$v$](img1132.gif)
il numero
(cardinale)
![$\deg(v)=\left\vert\{e\in E(G) \mid v\in e\}\right\vert$](img1357.gif)
. Diremo che
![$v$](img1132.gif)
ha
grado finito se
![$\deg(v)\in \mathbb{N}$](img1358.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
![\begin{displaymath}
\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)
\end{displaymath}](img1364.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$](img71.gif)
è un isomorfismo tra
![$G$](img3.gif)
e
![$G'$](img1135.gif)
e
![$v\in V(G)$](img1284.gif)
allora
![$\deg(v)=\deg(f(v))$](img1372.gif)
.
Definizione 17.5
Sia
![$G$](img3.gif)
un grafo finito e sia
![$V(G)=\{v_1,\dots,v_n\}$](img1373.gif)
, si chiama
score
di
![$G$](img3.gif)
la successione (finita)
![$n$](img2.gif)
-pla dei gradi dei suoi vertici ovvero
![% latex2html id marker 14397
$\mathop{\rm score}\nolimits (G)=(\deg(v_1),\dots,\deg(v_n))$](img1374.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'$](img1135.gif)
sono grafi isomorfi, allora
![% latex2html id marker 14409
$\mathop{\rm score}\nolimits (G)=\mathop{\rm score}\nolimits (G')$](img1376.gif)
.
Osservazione 17.7
Non è vero il viceversa del precedente teorema, si vedano ad esempio i grafi
i due grafi di figura
5 dell'esercizio
14.11.
Next: Lezione 18 (16 maggio
Up: Matematica Discreta
Previous: Lezione 16 (9 maggio
Luminati Domenico
2002-06-07