[Teoria, Algoritmi] Relazioni tra archi e nodi nei grafi

[xneo1]

Salve a tutti,
mi servirebbe una specie di elenco dove sono riportati, in base al tipo di grafo, le relazioni che ci sono tra archi e nodi.
1
Ad esempio in un grafo non orientato, connesso e aciclico il numero di archi è uguale al numero di nodi meno 1.

Ho provato a cercare in rete, ma non ho trovato nulla che mi soddisfacesse.
Grazie

[onlyReferee]

Ciao xneo
Cercando su google con la chiave di ricerca grafo relazioni archi nodi ho trovato diverso materiale (a meno che tu non lo abbia già visto e non ti soddisfi).
In caso negativo potrei sempre vedere di postare i miei vecchi appunti di analisi e progetto di algoritmi...

[xneo1]

Ti ringrazio, ma avevo già effettuato questo tipo di ricerca e non risolve il mio problema.

Ad esempio se che se un grafo non orientato è aciclico allora sarà necessariamente che m<=n-1, dove m è il numero degli archi e n il numero di nodi.

Purtroppo in rete non c'è niente del genere.

[apatriarca]

Non credo che esista una qualche tabella esaustiva con tutte le relazioni che cerchi. Per prima cosa le proprietà che puoi prendere in considerazione sono parecchie e dovresti considerarne le diverse combinazioni. Le relazioni che puoi poi scrivere per un qualche tipo di grafo sono inoltre parecchie e molto diverse tra di loro.

La relazione che hai scritto è comunque abbastanza facile da dimostrare. Ogni componente connessa del tuo grafo non orientato e aciclico è un albero. Siccome in un albero il numero di archi m è uguale a n-1 (dove n è il numero di nodi), avrai che il numero di archi totali M del grafo sarà M = \sum_i m_i dove la somma è su tutte le componenti connesse. Avrai quindi che M = \sum_i (n_i - 1) = N - C dove N è il numero di nodi del grafo e C è il numero di componenti connesse. Siccome C è almeno uguale a uno, si ottiene la relazione che hai scritto. Nota però che nella dimostrazione ho ottenuto una relazione molto più forte della tua. È infatti a questo punto possibile calcolare C = N - M per questo tipo di grafi.

[xneo1]

Quello era solo un esempio, poi non mi interessa la dimostrazione.
Lo so che ci sono parecchie relazioni, diciamo che a me interessano solo quelle più "evidenti" (e con questo ho detto tutto e non ho detto niente )

[apatriarca]

Sì.. Lo so che non ti interessava una dimostrazione. Volevo principalmente mostrare come ci sono molti modi diversi di scrivere la medesima relazione ed è certamente possibile scriverne altre. Una tabella di questo tipo non credo che esista. Queste informazioni le trovi però normalmente semplicemente cercando il particolare tipo di grafo su internet (soprattutto cercando in inglese).