Definizione di grafo come connessione o relazione tra oggetti
15 agosto 2013  //  By:   //  Development  //  No Comment   //   1199 Views

Un grafo come entità astratta può essere rappresentato come una relazione tra oggetti.

Viene definito come G= (V,E) nel quel V è un insieme di nodi o vertici, E è l’insieme delle coppie di nodi, detti archi.

I vertici rappresentano oggetti e gli archi relazioni tra essi.

Ne esistono due tipi:

  • Orientato, rappresenta relazioni orientate tra coppie di oggetti, ogni arco è orientato da uno dei due vertici. La direzione è indicata dalla freccia.

grafo_orientato

 

  • Non Orientato, o non diretto è quando gli archi non hanno direzioni e la relazione tra una coppia di nodi, che viene vista come un arco, è simmetrica.

Andiamo quindi ad identificare i nodi o vertici con n e con m il numero di archi.

Ora prendiamo in considerazione un arco del nostro grafo G di vertici (x,y).

Se il grafo è orientato l’arco esce da x ed entra in y; altrimenti x e y sono adiacenti.

Possiamo definire il grado di un vertice x come il #archi(m) incidenti su x; in questo caso per grafi non orientati a causa della simmetria si conta due volta cioè 2m.

Nel caso in cui il grafo sia orientato ci sarà quindi un grado in uscita ed un grado in entrata, per il grado totale ci sarà la somma dei due.

Cammini e cicli di un grafo G:

Un cammino in un grafo è una sequenza di vertici che va da es.(a,z) con <v0, v1, … , vk> i vertici del cammino.

In tale caso il cammino da (a,z) è lungo K, passa per i vertici <v0, …., vk> e gli archi sono (v0,v1), (v1,v2), … , (Vk-1, vk).

Se tutti i vertici sono distinti abbiamo un cammino semplice.

Nel caso in cui non sia orientato m<= (n-1)/2; in caso caso contratio cioè orientato per essere semplice

non deve passare due volte sullo stesso nodo  ed m <= n(n-1).

Come per il cammino il ciclo è semoplice nel caso in cui i nodi sono distinti e diretto aciclico quando è orientato e non contiene cicli.

Definizione di connettività di un grafo G:

Un grafo non orientato si dice connesso se esiste un cammino tra ogni coppia di vertici in G, cioè deve avere almeno (n-1) archi. E’ definito come Fortemente Connesso se esiste un cammino orientato tra ogni coppia di vertici in G.

es. se il vertice a è fortemente connesso a z allora ci devono essere cammini orientati da dal vertice a fino a z e viceversa.

Un sottografo di G è grafo Q i cui vertici e archi sono sottoinsieme dei vertici e degli archi di G. 

Operazioni possibili su un grafo:

dati: Insieme di vertici e di archi

Vertici() –> int: restituisce una collezione iterabile di tutti i vertici del grafo (#vertici);

Archi() –>  int: numero di archi;

Grado(vertice v) –> int: archi incidenti nel vertice v;

archiIncidenti(v) –> <v0, v1, … , Vk>: archi incidenti su v;

estremi(arco) –> <a,z>: restituisce gli estremi a e z dell’arco;

rimuoviVertice(v); rimuoviArco(arco); aggiungiVertice(v); opposto(v, arco); inserisciVertice(v);

scambia(arco,v): sostituisce l’elemento memorizzato nell’arco con v.

inserisciArco(a,z,v): inserisce e restituisce un nuovo arco non orientato avente per vertici a e z, contente v

 

 

About the Author :

BI CONSULTING. Studente di Ingegneria Informatica, Sistemista Linux e appassionato di tutto ciò che sia tecnologico ma soprattutto Open Source. Distro: Debian e Arch LInux. Smartphone: Nexus / Lg G2 Buona Lettura  Visualizza il profilo su Linkedln

Leave a reply