Next: Lezione 15
Up: Matematica Discreta (II modulo)
Previous: Lezione 13
Subsections
Definizione 14.1
Un grafo
![$ G$](img3.gif)
è una coppia ordinata
![$ G=(V,E)$](img1205.gif)
dove
![$ V$](img1206.gif)
è un insieme non
vuoto detto insieme dei
vertici del grafo ed
![$ E\subseteq
{V \choose 2}$](img1207.gif)
è detto l'insieme dei
lati. Se
![$ e=\{v_1,v_2\}=in E$](img1208.gif)
,
si dirà che il lato
congiunge i due vertici
![$ v_1$](img1210.gif)
e
![$ v_2$](img1211.gif)
e si
dirà anche che
![$ v_1$](img1210.gif)
e
![$ v_2$](img1211.gif)
sono gli
estremi del lato
![$ e$](img1209.gif)
.
Se
è un grafo, indicheremo con
l'insieme dei suoi vertici e con
l'insieme dei suoi lati, ovvero
.
Se
è un grafo e
si dirà
che
e
sono adiacenti o che
è vicino a
se
(cfr. esercizio 14.2).
Spesso i grafi sono rappresentati graficamente mediante dei punti a
rappresentare i vertici e delle linee congiungenti due vertici a rappresentare i
lati. Ad esempio in figura 2 sono rappresentati i
grafi
e
definiti da
Figura 2:
Esempi di grafi
![\begin{figure}\begin{center}
\psfig{file=esempiografo.ps,height=4cm} \end{center}\end{figure}](img1221.gif) |
Osservazione 14.2
Se
![$ G=(V,G)$](img1222.gif)
è un grafo, l'essere adiacenti, definisce una relazione su
![$ V$](img1206.gif)
detta
relazione d'adiacenza che denoteremo con
![$ \mathrel{{\cal R}(E)}$](img1223.gif)
. Ossia:
Tale relazione risulta essere oviamente
- simmetrica ossia
- antiriflessiva ossia
Viceversa, data una relazione simmetrica e antiriflessiva
sull'insieme
, l'insieme
è un sottinsieme
di
, e quindi
è un grafo.
Dimostrazione.
(1). Dalle definizioni si ha immediatamente che
e quindi
.
(2).
se e solo se
e
per definizione di
questo è vero se e solo se o
o
. Dato che la relazione
è simmetrica, ciò equivale a
dire
.
Osservazione 14.4
La proposizione precedente prova che dare un grafo i cui vertici sono
l'insieme
![$ V$](img1206.gif)
è equivalente a dare una relazione simmetrica e
antiriflessiva su
![$ V$](img1206.gif)
.
Osservazione 14.5
Si osservi che affinchè
![$ {\cal E}(\sim)$](img1239.gif)
sia l'insieme dei lati di un grafo è
necessario soltanto che
![$ \sim$](img945.gif)
sia antiriflessiva. La simmetria di
![$ \sim$](img945.gif)
è necessaria però per provare la seconda proprietà della proposizione
precedente.
Esercizio 14.1
Provare nel dettaglio quanto asserito nell'osservazione
14.2.
Soluzione
Esercizio 14.2
Sia
![$ V$](img1206.gif)
un insieme, e sia
![$ \sim$](img945.gif)
una relazione antiriflessiva su
![$ V$](img1206.gif)
. Si
provi che se
![$ \sim$](img945.gif)
non è simmetrica allora
![$ \mathrel{{\cal R}({\cal E}(\sim))}\ne\sim$](img1240.gif)
.
Si produca anche un esempio di relazione
su un insieme tale che
.
Soluzione
Definizione 14.6
Un
grafo diretto è una coppia
![$ (V,E)$](img1230.gif)
dove
![$ E\subset V\times V$](img1241.gif)
è
una relazione binaria su
![$ V$](img1206.gif)
.
Diamo alcuni esempi di grafi notevoli, per i quali esiste anche una notazione
standard.
Per ogni
indicheremo con
il grafo tale che
è detto il cammino di lunghezza
(i.e. ha
lati).
Indicheremo con
il grafo
è detto il cammino infinito.
Per ogni
,
indicheremo con
il grafo tale che
è detto il ciclo di lunghezza
(i.e. ha
lati e
vertici).
Per ogni
, indicheremo con
il grafo tale che
è detto il grafo completo su
vertici (i.e. ha tutti i lati
possibili che congiungono i suoi
vertici).
Per ogni
, indicheremo con
il grafo tale che
è detto il grafo completo bipartito su
ed
vertici
(i.e. ha tutti i lati possibili che congiungono i suoi primi
vertici con
gli altri
).
Definizione 14.8
Siano
![$ G=(V,E)$](img1205.gif)
e
![$ G=(V',E')$](img1274.gif)
due grafi, si dirà che
![$ G'$](img1219.gif)
è
sottografo di
![$ G$](img3.gif)
se e solo se
![$ V'\subseteq V$](img1275.gif)
e
![$ E'\subseteq E$](img1276.gif)
.
Definizione 14.9
Sia
![$ G=(V,E)$](img1205.gif)
un grafo e sia
![$ V'\subseteq V$](img1275.gif)
, chiameremo il
sottografo
indotto da
![$ G$](img3.gif)
su
![$ V'$](img1277.gif)
il grafo
![$ G[V']=(V',E\cap {V' \choose 2})$](img1278.gif)
.
Detto in altri termini nel sottografo indotto si mettono tutti i lati del grafo
che congiungono vertici di
.
Esercizio 14.3
Si provi che
![$ P_n$](img1249.gif)
è sottografo di
![$ C_n$](img1261.gif)
per ogni
![$ n$](img2.gif)
.
Soluzione
Esercizio 14.4
Sia
![$ m<n$](img1279.gif)
e sia
![$ V=\{1,\dots,m\}$](img1280.gif)
. Si determini il sottografo indotto da
![$ K_n$](img1265.gif)
su
![$ V$](img1206.gif)
.
Soluzione
Esercizio 14.5
Siano
![$ G,G',G''$](img1281.gif)
grafi e si provi che se
![$ G$](img3.gif)
è sottografo di
![$ G'$](img1219.gif)
e
![$ G'$](img1219.gif)
è
sottografo di
![$ G''$](img1282.gif)
allora
![$ G$](img3.gif)
è sottografo di
![$ G''$](img1282.gif)
.
Soluzione
Morfismi ed isomorfismo di grafi
Osservazione 14.11
Osserviamo che la condizione di essere un morfismo può essere espressa
anche dicendo che
![$\displaystyle \forall e\in E \quad f(e)\in E'$](img1286.gif)
ovvero
dove con
![$ f(e)$](img1288.gif)
si intende l'immagine mediante
![$ f$](img103.gif)
del sottinsieme
![$ e\subseteq V$](img1289.gif)
e con
![$ f(E)\subseteq 2^V$](img1290.gif)
l'insieme di tali immagini al
variare di
![$ e\in E$](img1291.gif)
. In simboli
![$ f(e)=\{f(v)\mid v\in e\}$](img1292.gif)
(ovvero se
![$ e=\{v_1,v_2\}$](img1293.gif)
allora
![$ f(e)=\{f(v_1),f(v_2)\}$](img1294.gif)
), e
![$ f(E)=\{f(e)\mid e\in
E\}$](img1295.gif)
.
Per questo motivo un morfismo sarà denotato anche con
.
Osservazione 14.12
Se
![$ {\cal R}$](img324.gif)
e
![$ {\cal R}'$](img1297.gif)
denotano le relazioni di adiacenza dei grafi
![$ G$](img3.gif)
e
![$ G'$](img1219.gif)
, la
proprietà di essere un morfismo si rienuncia in termini di
![$ {\cal R}$](img324.gif)
e
ed in questa forma può essere estesa ai grafi diretti.
Definizione 14.13
Un morfismo
![$ f:G\to G'$](img1299.gif)
si dice un
isomorfismo se
è bigettiva
è a sua volta un morfismo.
In tal caso i due grafi
e
si direnno isomorfi, e si
denoterà con
.
Proposizione 14.14
Siano
![$ G=(V,E)$](img1205.gif)
e
![$ G'=(V',E')$](img1283.gif)
due grafi. Una funzione
![$ f:V\to V'$](img1284.gif)
è un
isomorfismo se e solo se
è bigettiva
.
Dimostrazione.
Supponiamo che
sia un isomorfismo, allora per definizione
è
bigettiva. Dal fatto che
è un morfismo segue che se
, dal fatto che
è un morfismo segue allora che se
allora
, ma
e quindi è verificata la
(2).
Viceversa dalla (2) segue che se
allora
e quindi
è
un morfismo. Proviamo che
è a sua volta un morfismo. Sia
,
dato che
è bigettiva allora esiste
tale che
. Ma allora dalla (2) segue che
e quindi la tesi.
Esercizio 14.6
Si provi che
![$ K_{n,m}\oldcong K_{m,n}$](img1311.gif)
per ogni
![$ n,m\in \mathbb{N}$](img299.gif)
.
Soluzione
Esercizio 14.7
Siano
![$ G=(V,E)$](img1205.gif)
e
![$ G'=(V',E')$](img1283.gif)
due grafi. Si provi che se
![$ f:G\to G'$](img1299.gif)
è un
morfismo tale che
![$ f$](img103.gif)
è iniettiva e
![$ f(E)=E'$](img1312.gif)
allora
![$ f$](img103.gif)
è un isomorfismo.
Soluzione
Esercizio 14.9
Si provi che i due grafi rappresentati in figura
4 sono tra
loro isomorfi.
Figura:
I grafi di esercizio 14.9
![\begin{figure}\begin{center}
\mbox{\psfig{file=petersen1n.ps,width=5cm} %%
\psfig{file=petersen2n.ps,width=5cm}}
\end{center} \end{figure}](img1317.gif) |
Soluzione
Esercizio 14.10
Dire se i due grafi in figura
5 sono isomorfi oppure no.
Figura 5:
I grafi dell'esercizio 14.10
![\begin{figure}\begin{center}
\psfig{file=g1.ps,width=10cm} \end{center} \end{figure}](img1318.gif) |
Soluzione
Esercizio 14.11
Provare che i due grafi in figura
6 non sono isomorfi.
Figura 6:
I grafi dell'esercizio 14.11
![\begin{figure}\begin{center}
\psfig{file=g2.ps,width=10cm} \end{center} \end{figure}](img1319.gif) |
Soluzione
Esercizio 14.12
Sia
![$ G$](img3.gif)
il grafo dato dai vertici e dagli spigoli di un cubo e sia
![$ G'$](img1219.gif)
il
grafo tale che
![$ V(G')$](img1320.gif)
sia l'insieme delle parole di tre lettere nell'alfabeto
di due lettere
![$ \{a,b\}$](img1321.gif)
ed in cui due parole sono congiunte da un lato se e
solo se differiscono per una lettera soltanto. Si provi che
![$ G\oldcong G'$](img1300.gif)
.
Soluzione
Next: Lezione 15
Up: Matematica Discreta (II modulo)
Previous: Lezione 13
Domenico Luminati
2004-03-18