Perché è importante il diametro di un grafico casuale?
Riesco a vedere che il diametro di un grafico, definito come la lunghezza del percorso più breve e più lungo, è una quantità non banale in un grafico casuale , ad esempio il grafico casuale$G(n,p)$formato aggiungendo bordi tra$n$punti indipendentemente con probabilità$p$.
Ma cosa lo rende così matematicamente significativo? Quali relazioni ha con le altre idee grafiche fondamentali? Inoltre, se aggiungo qualche vincolo sul grafico, come la distribuzione dei gradi, o vincoli spaziali sui vertici (cioè grafico geometrico casuale), cosa fa questo al significato del diametro del grafico?
Risposte
Il diametro del grafico è di per sé significativo, così come lo è il numero cromatico o grado massimo. Se vuoi che il tuo grafico modelli una rete, ti dice il numero massimo di "salti" che uno deve prendere per andare da un nodo a qualsiasi altro. Se il tuo grafico è incorporato geometricamente come, diciamo, un grafico in cui ogni bordo è una linea retta di lunghezza 1, allora il diametro del grafico (astratto) è un limite superiore sul diametro del grafico incorporato, considerato come un sottoinsieme di$\mathbb{R}^n$.
Permettere$D$essere il diametro di un grafico,$n$il suo ordine,$\Delta$il suo massimo grado e$\kappa$la sua connettività. Alcune euristiche generali su come si comporta il diametro (queste sono tendenze, non teoremi):
- Se un grafo ha un diametro basso e molti vertici, allora deve avere molti spigoli, e questi spigoli devono essere distribuiti in modo un po' "uniforme" in modo da non permettere che due vertici siano distanti l'uno dall'altro.
- Se il diametro del grafico è molto grande rispetto al numero di vertici, allora il grafico ha meno spigoli.
- Analogamente ai punti precedenti, il diametro e il grado massimo insieme vincolano il numero totale di vertici che un grafico può avere. Euristicamente, non puoi ottenere più vertici da un grafico che se crei un albero di profondità$D$che si ramifica grossolanamente$\Delta-1$volte ad ogni strato, con alcuni bordi extra per chiudere le cose. Lo studio di questo limite è l'argomento del problema del diametro dei gradi .
- Mentre il diametro e il grado massimo sono vincolati$n$dall'alto, il diametro e la connettività lo legavano dal basso. Il limite sembra più o meno come$n \geq \kappa \cdot (D-1)$.
- Il diametro vincola anche la circonferenza del grafico. In breve, se il diametro è basso e il grafico contiene un ciclo qualsiasi, deve contenere un ciclo di breve durata.
Infine, il diametro agisce come un bel vincolo di complessità. Se stai cercando di studiare una struttura o una caratteristica nei grafici generali e ti stai perdendo irrimediabilmente, è spesso utile considerare cosa succede nei grafici di diametro 2 (specialmente dato qualche altro vincolo o classe di grafi ristretta che lo accompagna). Il che rende abbastanza fortuito che quasi tutti i grafici abbiano diametro 2!