Lezione 14 (2 maggio 2000 h. 11-13)

Definizione di grafo

Definizione 14.1   Un grafo G è una coppia ordinata G=(V,E) dove V è un insieme 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₂.

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

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 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 2: Esempi di grafi

Esercizio 14.1      Sia (V,E) un grafo e si definisca la relazione $\mathrel{{\cal R}(E)}$ su V ponendo

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

Si provi che:

1.

$\mathrel{{\cal R}(E)}$ è simmetrica (i.e. $v_1 \mathrel{{\cal R}(E)} v_2 \Rightarrow v_2 \mathrel{{\cal R}(E)} v_1$)

2.

$\mathrel{{\cal R}(E)}$ è antiriflessiva (i.e. $\forall v\quad \lnot\, v \mathrel{{\cal R}(E)} v$)

La relazione $\mathrel{{\cal R}(E)}$ è a volte detta relazione di adiacenza.
Soluzione

Esercizio 14.2      Sia V un insieme, e sia $\sim$ una relazione antiriflessiva su V. Si definisca ${\cal E}(()\sim)=\{\{v_1,v_2\}\mid v_1\sim v_2\}$. Si provi che $(V,{\cal E}(\sim))$ è un grafo.
Soluzione

Esercizio 14.3    Con riferimento ai due esercizi precedenti, si provi 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$.

Soluzione

Osservazione 14.2   Gli esercizi precedenti provano che dare un grafo i cui vertici sono l'insieme V è equivalente a dare una relazione simmetrica e antiriflessiva su V.

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) & = & \{0,1,2,\dots,n\} \\ E(P_n) & = & \bigl\{\{i,i+1\} \bigm \vert i=0,1,\dots,n-1\bigr\} \end{eqnarray*}$$

P_n è detto il cammino di lunghezza n (i.e. ha n 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 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) & = & \{u_1,u_2,\dots,u_n\}\cup \{v_1,v_2,\dots,v_m\}\\ ... ... & \bigl\{\{u_i,v_j\} \bigm \vert i=1,\dots,n,j=1,\dots,m\bigr\} \end{eqnarray*}$$

K_n è 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).

   
Isomorfismo di grafi

Definizione 14.3   Due grafi G=(V,E) e G'=(V',E') si dicono isomorfi, e si denoterà con $G\oldcong G'$, se e siste una bigezione $f:V\to V'$ tale che $e\in E\iff f(e)\in E'$, dove se $e=\{x,y\}$ si è denotato $f(e)=\{f(x),f(y)\}$. Una tale applicazione f sarà detta un isomorfismo tra G e G'.

Esercizio 14.4    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.5      Si provi che i due grafi rappresentati in figura 3 sono tra loro isomorfi.

  

Figure 3: I grafi di esercizio 14.5

Soluzione

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

  

Figure 4: I grafi dell'esercizio 14.6

Soluzione

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

  

Figure 5: I grafi dell'esercizio 14.7

Soluzione

Esercizio 14.8      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

Una stima del numero di grafi non isomorfi su n vertici