Grafi molto connessi

[Anér]

Visto che è semplicissimo lasciatelo a chi è alle prime armi (ma se siete alle prime armi fatene uso).

Siano n, k due naturali (eventualmente uguali). Determinare quanti archi deve avere come minimo un grafo su n vertici se vogliamo che per ogni coppia di vertici A e B ci sia un percorso lungo al più k che li collega.

[Gottinger95]

Se k=1, allora tutti i nodi devono essere collegati fra loro, perciò gli archi sono n (n - 1) / 2 . Se k > 1, immaginiamo un grafo in cui tutti gli n - 1 archi abbiano come primo estremo V1 e come secondo estremo Vi, con i = 2, .., n . Se il nodo di partenza è V1 si raggiunge ovviamente ogni altro nodo B in un passo. Altrimenti se il nodo si partenza non è V1, nel primo passo si va a V1 e nel secondo si può raggiungere un qualsiasi nodo B. Gli archi non possono essere meno di n - 1, altrimenti il grafo non sarebbe connesso. Se il grafo non fosse connesso, aldilà del valore di k, non sarebbe possibile raggiungere il nodo non connesso.
Riassumendo:
- k = 1 --> n(n-1)/2
- k > 1 --> n-1
Scusatemi se non so ancora usare la tex