Cos'è multigrafo?

Multigrafo

Un multigrafo è un tipo di https://it.wikiwhat.page/kavramlar/grafo, in cui più https://it.wikiwhat.page/kavramlar/archi (detti anche spigoli) possono collegare la stessa coppia di https://it.wikiwhat.page/kavramlar/vertici. In altre parole, tra due vertici può esistere più di un arco.

Caratteristiche principali:

• Archi multipli: La caratteristica distintiva di un multigrafo è la possibilità di avere https://it.wikiwhat.page/kavramlar/archi%20multipli tra una stessa coppia di vertici. Questi archi multipli sono distinti l'uno dall'altro, anche se collegano gli stessi vertici.
• Cicli: Un multigrafo può contenere https://it.wikiwhat.page/kavramlar/cicli, sia semplici che formati da archi multipli tra due vertici.
• Loop: Come un grafo standard, un multigrafo può anche avere https://it.wikiwhat.page/kavramlar/loop, ovvero archi che collegano un vertice a sé stesso.

Rappresentazione:

A causa della possibilità di archi multipli, la rappresentazione di un multigrafo tramite una matrice di adiacenza deve essere modificata. Invece di memorizzare solo 0 o 1 per indicare l'assenza o la presenza di un arco, la matrice di adiacenza di un multigrafo memorizza il numero di archi tra due vertici.

Applicazioni:

I multigrafi sono utili per modellare situazioni in cui le relazioni tra entità possono essere multiple. Esempi includono:

• Reti di trasporto: Archi multipli possono rappresentare diverse rotte tra due città.
• Reti sociali: Archi multipli possono indicare diversi tipi di interazione tra due persone.
• Circuiti elettrici: Archi multipli possono rappresentare più fili che collegano due componenti.

Distinzione da altri tipi di grafo:

• Un grafo semplice non permette archi multipli né loop.
• Uno pseudografo permette sia archi multipli che loop. Quindi, ogni multigrafo è anche uno pseudografo, ma non viceversa.
• Un digrafo (grafo diretto) ha archi diretti, mentre un multigrafo può essere diretto o non diretto. Se è diretto e permette archi multipli, viene chiamato multidigrafo.