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_1$ e $v_2$ e si dirà anche che $v_1$ e $v_2$ 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}$$

Figura 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).

Figura 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\ge3$ 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 $n$ vertici).

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 $G[V']=(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.

Figura: I grafi di esercizio 14.9

Soluzione

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

Figura 4: I grafi dell'esercizio 14.10

Soluzione

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

Figura 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