Lezione 14 (2 maggio 2001 h. 10.30-12.30)

Definizione di grafo

Definizione 14.1   Un grafo G è una coppia ordinata G=(V,E) dove V è un insieme non vuoto detto insieme dei vertici del grafo ed $E\subseteq {V \choose 2}$ è detto l'insieme dei lati. Se $e=\{v_1,v_2\}=in E$, si dirà che il lato e congiunge i due vertici v₁ e v₂ e si dirà anche che v₁ e v₂ sono gli estremi del lato e.

Se G è un grafo, indicheremo con V(G) l'insieme dei suoi vertici e con E(G) l'insieme dei suoi lati, ovvero G=(V(G),E(G)).

Se G=(V,E) è un grafo e $v,v'\in V$ si dirà che v e v' sono adiacenti o che v' è vicino a v se $\{v,v'\}\in E$ (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 1 sono rappresentati i grafi G e G'definiti da

$$\begin{array}{rclcrcl} V(G) & = & \{1,2,3,4\} &\quad E(G) &... ...3\},\{2,3\},\{3,4\},\{3,5\},\{4,5\},\{2,4\}\big\}. \end{array}$$

  

Figure 1: Esempi di grafi

Osservazione 14.2   Se G=(V,G) è un grafo, l'essere adiacenti, definisce una relazione su V detta relazione d'adiacenza che denoteremo con $\mathrel{{\cal R}(E)}$. Ossia:

$$v_1 \mathrel{{\cal R}(E)} v_2 \iff \{v_1,v_2\}\in E.$$

Tale relazione risulta essere oviamente

• simmetrica ossia $v_1 \mathrel{{\cal R}(E)} v_2 \Rightarrow v_2 \mathrel{{\cal R}(E)} v_1$
• antiriflessiva ossia $\forall v\quad \lnot\, v \mathrel{{\cal R}(E)} v$

Viceversa, data una relazione simmetrica e antiriflessiva $\sim$ sull'insieme V, l'insieme ${\cal E}(()\sim)=\{\{v_1,v_2\}\mid v_1\sim v_2\}$ è un sottinsieme di ${V \choose 2}$, e quindi $(V,{\cal E}(()\sim)$ è un grafo.

Proposizione 14.3   Con le notazioni appena introdotte si ha che

1.

Se (V,E) è un grafo allora ${\cal E}(\mathrel{{\cal R}(E)}) = E$

2.

Se $\sim$ è una relazione simmetrica e antiriflessiva su V allora $\mathrel{{\cal R}({\cal E}(\sim))}=\sim$.

Dimostrazione.  (1). Dalle definizioni si ha immediatamente che

$$\{v_1,v_2\}\in{\cal E}(\mathrel{{\cal R}(E)}) \iff v_1 \mathrel{{\cal R}(E)} v_2 \iff \{v_1,v_2\}\in E$$

e quindi ${\cal E}(\mathrel{{\cal R}(E)}) = E$.

(2). $v_1 \mathrel{{\cal R}({\cal E}(\sim))} v_2$ se e solo se $\{v_1,v_2\}\in {\cal E}(\sim)$ e per definizione di ${\cal E}(()\sim)$ questo è vero se e solo se o $v_1\sim v_2$ o $v_2 \sim v_1$. Dato che la relazione $\sim$ è simmetrica, ciò equivale a dire $v_1\sim v_2$.     $\square$

Osservazione 14.4   La proposizione precedente prova che dare un grafo i cui vertici sono l'insieme V è equivalente a dare una relazione simmetrica e antiriflessiva su V.

Osservazione 14.5   Si osservi che affinchè ${\cal E}(()\sim)$ sia l'insieme dei lati di un grafo è necessario soltanto che $\sim$ sia antiriflessiva. La simmetria di $\sim$ è 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 un insieme, e sia $\sim$ una relazione antiriflessiva su V. Si provi che se $\sim$ non è simmetrica allora $\mathrel{{\cal R}({\cal E}(\sim))}\ne\sim$.

Si produca anche un esempio di relazione $\sim$ su un insieme tale che $\mathrel{{\cal R}({\cal E}(\sim))}\ne\sim$.
Soluzione

Definizione 14.6   Un grafo diretto è una coppia (V,E) dove $E\subset V\times V$ è una relazione binaria su V.

Osservazione 14.7   Intuitivamente un grafo diretto può essere pensato come un grafo, in cui sono specificati dei ``versi di percorrenza'' degli archi che congiungono due punti. In questa ottica denoteremo anche con $v\to w$ il fatto che $(v,w)\in E$.

Si osservi che, a differenza dei grafi dove tra due vertici cè soltanto un lato e non ci sono lati che vanno da un vertice a se stesso, tra due vertici v e w di un grafo diretto ci possono essere entrambi i lati $v\to w$ e $w\to v$, e si possono avere anche lati del tipo $v\to v$ (vedi figura 2).

  

Figure 2: Un grafo diretto

Si noti però che l'osservazione 14.4 mostra che dare un grafo è equivalente a dare un grafo diretto simmetrico (i.e. se $v\to w$ anche $w\to v$) e antiriflessivo (i.e. $v\not\to v$ per ogni v). In altri termini la nozione di grafo diretto è una estensione di quella di grafo.

Alcuni grafi notevoli

Diamo alcuni esempi di grafi notevoli, per i quali esiste anche una notazione standard.

Per ogni $n\in\mathbb N$ indicheremo con P_n il grafo tale che

$$\begin{eqnarray*}V(P_n) & = & \{1,2,\dots,n\} \\ E(P_n) & = & \bigl\{\{i,i+1\} \bigm \vert i=1,\dots,n-1\bigr\} \end{eqnarray*}$$

P_n è detto il cammino di lunghezza n-1 (i.e. ha n-1 lati).

Indicheremo con $P_\infty$ il grafo

$$\begin{eqnarray*}V(P_\infty) & = & \mathbb N\\ E(P_\infty) & = & \bigl\{\{i,i+1\} \bigm \vert i\in\mathbb N\bigr\} \end{eqnarray*}$$

P_n è detto il cammino infinito.

Per ogni $n\in\mathbb N$, $n\ge 3$ indicheremo con C_n il grafo tale che

$$\begin{eqnarray*}V(C_n) & = & \{1,2,\dots,n\} \\ E(C_n) & = & \bigl\{\{i,i+1\} \bigm \vert i=1,\dots,n-1\bigr\} \cup \bigl\{\{1,n\}\bigr\} \end{eqnarray*}$$

C_n è detto il ciclo di lunghezza n (i.e. ha n lati e nvertici).

Per ogni $n\in\mathbb N$, indicheremo con K_n il grafo tale che

$$\begin{eqnarray*}V(K_n) & = & \{1,2,\dots,n\} \\ E(K_n) & = & \displaystyle {V(K_n) \choose 2} \end{eqnarray*}$$

K_n è detto il grafo completo su n vertici (i.e. ha tutti i lati possibili che congiungono i suoi n vertici).

Per ogni $n,m\in\mathbb N$, indicheremo con K_n,m il grafo tale che

$$\begin{eqnarray*}V(K_{n,m}) & = & \{1,2,\dots,n\}\cup \{n+1,n+2,\dots,n+m\}\\ ... ... & \bigl\{\{i,j\} \bigm \vert i=1,\dots,n,j=n+1,\dots,n+m\bigr\} \end{eqnarray*}$$

K_n,m è detto il grafo completo bipartito su n ed m vertici (i.e. ha tutti i lati possibili che congiungono i suoi primi n vertici con gli altri m).

Sottografi e sottografi indotti

Definizione 14.8   Siano G=(V,E) e G=(V',E') due grafi, si dirà che G' è sottografo di G se e solo se $V'\subseteq V$ e $E'\subseteq E$.

Definizione 14.9   Sia G=(V,E) un grafo e sia $V'\subseteq V$, chiameremo il sottografo indotto da G su V' il grafo $(V',E\cap {V' \choose 2})$.

Detto in altri termini nel sottografo indotto si mettono tutti i lati del grafo G che congiungono vertici di V'.

Esercizio 14.3    Si provi che P_n è sottografo di C_n per ogni n.
Soluzione

Esercizio 14.4    Sia m<n e sia $V=\{1,\dots,m\}$. Si determini il sottografo indotto da K_n su V.
Soluzione

Esercizio 14.5    Siano G,G',G'' grafi e si provi che se G è sottografo di G' e G' è sottografo di G'' allora G è sottografo di G''.
Soluzione

   
Morfismi ed isomorfismo di grafi

Definizione 14.10   Siano G=(V,E) e G'=(V',E') due grafi. Una funzione $f:V\to V'$ è detta un morfismo di grafi se

$$\forall v_1,v_2\in V\quad \{v_1,v_2\}\in E \Rightarrow\{f(v_1),f(v_2)\}\in E'.$$

Osservazione 14.11   Osserviamo che la condizione di essere un morfismo può essere espressa anche dicendo che

$$\forall e\in E \quad f(e)\in E' \quad \hbox{\rm {ovvero}} \quad f(E)\subseteq E'$$

dove con f(e) si intende l'immagine mediante f del sottinsieme $e\subseteq V$ e con $f(E)\subseteq 2^V$ l'insieme di tali immagini al variare di $e\in E$. In simboli $f(e)=\{f(v)\mid v\in e\}$ (ovvero se $e=\{v_1,v_2\}$ allora $f(e)=\{f(v_1),f(v_2)\}$), e $f(E)=\{f(e)\mid e\in E\}$.

Per questo motivo un morfismo sarà denotato anche con $f:(V,E)\to (V',E')$.

Osservazione 14.12   Se $\cal R$ e ${\cal R}'$ denotano le relazioni di adiacenza dei grafi G e G', la proprietà di essere un morfismo si rienuncia in termini di $\cal R$ e ${\cal R}'$

$$\forall v_1,v_2\in V\quad v_1 {\cal R}v_2 \Rightarrow f(v_1) {\cal R}' f(v_2)$$

ed in questa forma può essere estesa ai grafi diretti.

Definizione 14.13   Un morfismo $f:G\to G'$ si dice un isomorfismo se

1.

f è bigettiva

2.

f^-1 è a sua volta un morfismo.

In tal caso i due grafi G e G' si direnno isomorfi, e si denoterà con $G\oldcong G'$.

Proposizione 14.14   Siano G=(V,E) e G'=(V',E') due grafi. Una funzione $f:V\to V'$ è un isomorfismo se e solo se

1.

f è bigettiva

2.

$\forall e$ $e\in E\iff f(e)\in E'$.

Dimostrazione.  Supponiamo che f sia un isomorfismo, allora per definizione f è bigettiva. Dal fatto che f è un morfismo segue che se $e\in E \Rightarrow f(e)\in E'$, dal fatto che f^-1 è un morfismo segue allora che se $f(e)\in E'$ allora $f^{-1}(f(e))\in E$, ma f^-1(f(e))=e e quindi è verificata la (2).

Viceversa dalla (2) segue che se $e\in E$ allora $f(e)\in E'$ e quindi f è un morfismo. Proviamo che f^-1 è a sua volta un morfismo. Sia $e'\in E$, dato che f è bigettiva allora esiste $e\in {V \choose 2}$ tale che e' = f(e). Ma allora dalla (2) segue che $e=f^{-1}(e')\in E$ e quindi la tesi.     $\square$

Esercizio 14.6    Si provi che $K_{n,m}\oldcong K_{m,n}$ per ogni $n,m\in\mathbb N$.
Soluzione

Esercizio 14.7    Siano G=(V,E) e G'=(V',E') due grafi. Si provi che se $f:G\to G'$ è un morfismo tale che f è iniettiva e f(E)=E' allora f è un isomorfismo.
Soluzione

Esercizio 14.8      Si provi che:

1.

L'identità è un isomorfismo tra G e se stesso (quindi $G\oldcong G$).

2.

Se f è un isomorfismo tra G e G' allora f^-1 è un isomorfismo tra G' e G (quindi $G\oldcong G'$ allora $G'\oldcong G$).

3.

Se f è un isomorfismo tra G e G' e g è un isomorfismo tra G' e G'' allora $G\circ f$ è un isomorfismo tar G e G'' (quindi $G\oldcong G'$ e $G'\oldcong G''\Rightarrow G \oldcong G''$).

Soluzione

Esercizio 14.9      Si provi che i due grafi rappresentati in figura 3 sono tra loro isomorfi.

  

Figure 3: I grafi di esercizio 14.9

Soluzione

Esercizio 14.10      Dire se i due grafi in figura 4 sono isomorfi oppure no.

  

Figure 4: I grafi dell'esercizio 14.10

Soluzione

Esercizio 14.11      Provare che i due grafi in figura 5 non sono isomorfi.

  

Figure 5: I grafi dell'esercizio 14.11

Soluzione

Esercizio 14.12      Sia G il grafo dato dai vertici e dagli spigoli di un cubo e sia G' il grafo tale che V(G') sia l'insieme delle parole di tre lettere nell'alfabeto di due lettere $\{a,b\}$ 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'$.
Soluzione