Gli archi del grafo
Cos'è un arco del grafo
Un arco è una relazione binaria tra due vertici di un grafo. E' anche detto spigolo o lato.
La differenza tra archi e spigoli
In genere si parla di arco nei grafi orientati (digrafi) mentre di spigoli nei grafi non orientati.
Ecco un esempio pratico di spigolo
In un arco, invece, è presente anche un verso.
Nota. Nel caso degli archi gli estremi sono detti nodi. Va comunque detto che in alcuni libri di testo si parla di nodi a archi anche per intendere anche i vertici e gli spigoli.
Un arco/spigolo si indica ponendo tra parentesi tonde i due vertici che congiunge separati da una virgola.
$$ α = (1,2) $$
Posso anche indicare l'arco o lo spigolo semplicemente scrivendo (1,2) senza assegnare un'etichetta al lato. E' lo stesso.
$$ (1,2) $$
Nota. I vertici dell'arco (1,2) formano una coppia ordinata del prodotto cartesiano VxV ( dove V è l'insieme dei vertici del grafo ) in quanto è presente una direzione e un verso. I vertici dello spigolo, invece, formano una coppia non ordinata perché non è presente un verso. Nel caso dello spigolo le notazioni (1,2) o (2,1) sono equivalenti e indicano lo stesso spigolo in entrambi i versi.
Gli estremi, l'arco incidente
Gli estremi di un arco sono i vertici che congiunge
Nel caso degli archi gli estremi sono detti nodi.
L'arco tra due nodi è detto incidente.
Nel caso degli spigoli, invece, gli estremi sono detti vertici.
Allo stesso modo è detto incidente anche lo spigolo tra due vertici.
Tipi di archi: anelli, adiacenti
Se un arco/spigolo ha gli estremi coincidenti in un solo vertice si dice anello.
Due archi/spigoli sono detti adiacenti se hanno un vertice estremo in comune.
In questo esempio gli spigoli (1,2) e (2,3) hanno il vertice 2 come estremo in comune.
La dimensione del grafo
Un grafo è composto da un numero finito (m) di archi/spigoli.
L'insieme di tutti gli archi/spigoli del grafo G si indica con le lettere E o ε
Il numero (m) degli archi/spigoli determina la dimensione del grafo.
Esempio
Questo grafo è composto dalle coppie (a,b) , (a,c), (b,d), (c,d), (c,e), (d,f), (e,f).
Essendo spigoli non hanno un verso.
Pertanto, lo spigolo (a,b) comprende anche il verso opposto (b,a).
Il sottoinsieme di archi del grafo
Un sottoinsieme W di archi/spigoli del grafo si indica allo stesso modo.
Dove W è un sottoinsieme del grafo G.
Il sottoinsieme E(W) include gli archi/spigoli di G che hanno entrambi gli estremi nel sottoinsieme W.
Esempio
Il sottoinsieme W è composto dagli spigoli (a,b), (a,c), (b,d), (c,d).
