Concetti

Tra i termini relativi ai grafi ci sono:

• Adiacenza e incidenza

  Due nodi $v$ e $u$ sono adiacenti se esiste un arco $(u,v)\in E$, che a sua volta è detto incidente a $v$ e $u$.

• Intorno

  L'intorno di un vertice $u\in V$ sono quei vertici che gli sono adiacenti: $$N(u)=\left\{v\in V|(u,v)\in E\right\}$$

• Densità

  La densità di un grafo $0\le \delta (G)\le 1$ indica il rapporto tra $|E|$ e il numero totale di possibili archi, per cui la funzione diventa $\delta (G)=\frac{m}{n^2}$ se orientato e $\delta (G)=\frac{2m}{n(n-1)}$ se non orientato.

  Il grafo è detto sparso se $\delta (G)\to 0$ e quindi $|E|\approx |V|$, e denso se $\delta (G)\to 1$ ovvero se $|E|\approx |V^2|$. Se $\delta (E_n)=0$ il grafo $E_n$ si dice vuoto, mentre se $\delta (K_n)=1$ il grafo $K_n$ si dice completo.

• Peso

  Un grafo si dice pesato se $G=(V,E,w)$ dove $w$ è una funzione peso che assegna ai vertici, se $w:V\to \mathbb{R}$, o agli archi, se $w:E\to \mathbb{R}$, un valore reale chiamato peso.

• Sottografo

  Un grafo $G^{\prime }=(V^{\prime },E^{\prime })$ è sottografo di $G=(V,E)$ se: $$V^{\prime }\subseteq V\wedge E^{\prime }\subseteq E\cap V^{\prime 2}$$ ed è detto sottografo indotto $E^{\prime }=E\cap V^{\prime 2}$ con notazione $G^{\prime }=G[V^{\prime }]$.

  Per esempio dal primo grafo, il secondo è sottografo e il terzo è sottografo indotto:

  

• Cammino

  Per i grafi, un cammino è detto semplice quando ogni nodo è distinto, ed è un ciclo se $n_0=n_k$.

• Connessione

  Un grafo è connesso se per ogni $u,v\in V$ esiste un cammino $(u,...,v)$, altrimenti è disconnesso.

  Si dice poi componente connessa (c.c.) il sottoinsieme $V^{\prime }\subseteq V$ per cui:

  1. $G[V^{\prime }]$ è connesso
  2. $V^{\prime }\not\subset V^{\prime \prime }$ se un $G[V^{\prime \prime }]$ è connesso, per cui $V^{\prime }$ non fa parte di una c.c. più grande

  Il numero di componenti connesse è $\mathrm{NCC}(G)$, e insieme formano una partizione di $V$.

  Per esempio nel seguente grafo ci sono tre componenti connesse:

  

• Complemento

  Un grafo $\bar{G}=(V,\bar{E})$ è complemento di $G=(V,E)$ se: $$\forall (u,v)\in \bar{E},(u,v)\notin E$$ infatti ${\bar{K}}_n=E_n$, ovvero il grafo completo è complemento di quello vuoto.

  Per esempio, il primo grafo è complemento del secondo e viceversa:

  

  L'unica relazione vincolante di connessione tra $G$ e $\bar{G}$ è quella per cui se $G$ è disconnesso allora $\bar{G}$ sarà connesso, perchè in $\bar{G}$ i nodi saranno interconnessi attraverso componenti connesse diverse in $G$.

• Grafo bipartito

  Un grafo è bipartito se può essere diviso in due parti in cui non ci sono archi.

  Per esempio, in questo grafo i vertici di ogni suddivisione non sono adiacenti:

  

• Clique

  Si definisce clique un qualunque sottografo completo di $G$, ed è detta massima quando ha il massimo numero di vertici, e massimale quando non è contenuta in un'altra più grande.

  Il numero di nodi della clique massima nel grafo $G$ viene espresso come $\omega (G)$.

  Per esempio, il grafo

  

  possiede $5$ clique di cui $2$ massimali (i.e. verde e arancione) di cui una è massima (i.e. verde).