[Algo] Ponti e punti di articolazione

[Pablitos23]

Dimostrare o confutare che esiste un grafo G con la proprietà di avere un arco la cui eliminazione fa aumentare di 2 il numero dei suoi punti di articolazione e di 3 il numero dei suoi ponti.

Potreste aiutarmi almeno a cominciare? Ne so poco sui ponti e punti di articolazione.

Buona giornata.

[apatriarca]

Ci provo anche se questi concetti non mi sono particolarmente familiari.

Partiamo dai ponti. Sono semplicemente degli archi che non appartengono a nessuno ciclo. Se il numero di ponti aumenta di 3 vuol dire che c'erano 3 archi "in serie" nel ciclo con l'arco rimosso. Se infatti non fossero tali ci sarebbero ancora dei cicli. Il problema dei punti di articolazione a questo punto è che ogni vertice di un ponte è un punto di articolazione se ha grado maggiore di uno. Ma questa condizione è facilmente verificata nel nostro caso. I due vertici dell'arco originale sono infatti di grado uno, mentre gli altri due interni al nostro ciclo saranno di grado almeno due.

È insomma sufficiente che ci sia un ciclo di 4 archi e due vertici adiacenti in questo ciclo siano di grado 2. Il caso più semplice è ovviamente quello di un semplice ciclo.

[Pablitos23]

Questa penso sia la soluzione che hai dedotto, dove i nodi azzurri sono i 2 punti di articolazione e gli archi neri i 3 ponti dopo l'eliminazione dell'arco marroncino.