Grafi poco connessi

[darkcrystal]

E' possibile costruire un grafo finito e connesso tale che ogni vertice abbia grado almeno 2, ma tale che cancellando un vertice qualsiasi diventi disconnesso?

[Decan]

Uhm, facile ma bellino! E' tuo?

Che ogni vertice ha grado >=2 implica che il grafo contiene un ciclo (basta partire da un qualunque vertice e percorrere successivamente dei lati, scegliendoli arbitrariamente: prima o poi si torna ad un vertice per cui si è già passati). Sia A uno dei vertici che fanno parte di questo ciclo. Togliendo A dobbiamo avere un grafo disconnesso, cioè A "tiene uniti" due o più sotto-grafi connessi che altrimenti sarebbero isolati tra loro. Ciò è possibile se uno o più di questi sotto-grafi è "appeso" ad A, cioè nessuno dei suoi vertici fa parte del ciclo appena trovato. Perciò ad ogni vertice del ciclo devono essere appesi uno o più sotto-grafi isolati.
Sia B un vertice connesso con A di un sotto-grafo appeso ad A. Percorriamo il lato da A a B e poi continuiamo il percorso arbitariamente (sfruttando il fatto che tutti i vertici hanno grado >=2): prima o poi torniamo ad A o ad un vertice del sotto-grafo per cui si è già passati. Ma allora in questo sotto-grafo (includendo ora in esso anche il vertice A) c'è un ciclo, a ciascuno dei cui vertici, per il ragionamento di cui sopra, deve essere appeso un "sotto-sotto-grafo" isolato dagli altri, nel quale c'è ancora un ciclo... insomma, avremmo bisogno di avere infiniti vertici nel grafo perché esso rispetti le condizioni della traccia.

[/quote]

[darkcrystal]

Si, è mio... così, un'idea sparsa...
Ah, dai, bonus question: usare questo fatto per l'altro problema di questa sezione, quello di Leblanc...

[Decan]

Bien, ci penserò

[Catraga]

Quello che andavate crecando e' la costruzione di grafi con costante di connessione pari a 1...
Piu' in generale se da un grafo togliendo k vertici qualsiasi, ma non meno, lo si rende sconnesso si dice che ha costante di connessione k.
La questione e' molto importante per quello che riguarda la progettazione di reti (soprattutto wireless...).

[Marco]

Ciao. un po' di considerazioni sparse su questo graziosissimo problema.

1. L'ipotesi

tale che ogni vertice abbia grado almeno 2

è superflua: se un vertice ha grado 0, è un vertice isolato e il grafo non è connesso, oppure è il grafo banale con un solo vertice e non verifica l'ipotesi di disconnettersi cancellando un nodo.

Se invece un nodo ha grado 1, è una "penisola" agganciata ad un grafo altrimenti connesso. E' chiaro che cancellando tale nodo, non si disconnette.

2.

ogni vertice ha grado >=2 implica che il grafo contiene un ciclo

Questo fatto si dimostra immediatamente, ricordando che un grafo senza cicli è un albero e un albero connesso con N nodi ha esattamente N-1 archi. Non mi è del tutto chiaro dove usi l'esistenza di un ciclo.

3. La dimostrazione di Decan non mi torna:

Ma allora in questo sotto-grafo [...] c'è un ciclo, a ciascuno dei cui vertici, per il ragionamento di cui sopra, deve essere appeso un "sotto-sotto-grafo"...

Per poter applicare "il ragionamento di cui sopra" ti devi sincerare che le ipotesi siano soddisfatte. In questo caso l'ipotesi che salta è che si disconnetta cancellando un vertice: nel sottografo, A ha grado 1, quindi cancellandolo il grafo resta connesso. Anche non considerando A dentro al sottografo, non si aggira il problema. Potrebbe darsi infatti che cancellando B il sottografo non si disconnetta.

4. In conclusione, direi che il claim "un tale grafo non esiste" resta valido, ma (a meno di lampi di genio che a me non son venuti) non è così ovvio da dimostrare in due balletti.

[Marco]

Ok. Sembra che la cosa non interessi più a nessuno.

Ieri notte ho scritto per benino la mia sol. Non è difficile e grosso modo sfrutta le stesse idee di Decan, ma ci sono un sacco di dettaglietti noiosi da curare. Mi aiuto con una manciata di

Definizioni. Un grafo è detto poco connesso [p.c.] se verifica le ipotesi del problema (è connesso, selezionando un qualunque vertice si disconnette) e in più ha almeno due nodi [ipotesi di comodo, per evitare banalità].

Un grafo è detto quasi poco connesso [q.p.c.] se è connesso, ha almeno due nodi e, selezionando un qualunque vertice tranne al più uno si disconnette. Tale nodo (quando esiste) è detto nodo eccezionale. I nodi non eccezionali sono detti comuni.

Si vede subito che un grafo p.c. è anche q.p.c.

La tesi che vogliamo dimostrare è che non esistono grafi finiti poco connessi. Dimostrerò in verità una tesi più forte:

Claim: Non esistono grafi finiti quasi poco connessi.

Supponiamo il contrario. Tra tutti i grafi q.p.c. [da qui in poi, tutti i grafi sono intesi come grafi finiti], ne esisterà uno con il numero minimo possibile di nodi e di archi, che chiamo G.

Lemma dei gradi Un nodo comune di un grafo q.p.c. ha grado almeno 2.

Dimostrato nel mio primo post. []

Definizione. Ognuna delle componenti connesse ottenuta da un grafo q.p.c. cancellando un nodo comune A è detta A-porzione.

Lemma di struttura Consideriamo un nodo comune A del grafo G. Sia C una A-porzione. Allora esiste un unico arco che congiunge C con A. Come corollario, le A-porzioni sono tante quante il grado di A.

Consideriamo gli archi che vanno da C ad A. Se non esistessero, allora G risulterebbe inizialmente disconnesso (gli unici archi cancellati escono da A e sarebbe perciò impossibile andare da un qualunque nodo di C ad A). Ma G è connesso per ipotesi.

Se invece esistesse più di un arco da C ad A, allora cancellandoli tutti tranne uno, otterremmo un nuovo grafo G' che risulta essere q.p.c., ma con un numero di archi inferiore, contro l'ipotesi di minimalità di G. []

Definizione. Una A-porzione è comune se tutti i suoi vertici sono comuni. Altrimenti, se la porzione contiene l'eventuale nodo eccezionale, è detta eccezionale.

Lemma delle porzioni comuni Sia A un nodo comune di G. Allora le A-porzioni comuni sono sottografi che sono a loro volta q.p.c.

Sia C una A-porzione. Essa può avere un solo nodo, oppure più di uno.

Se C si riduce ad un nodo singolo, C è congiunto al solo vertice A, quindi ha grado 1. Per il lemma dei gradi, deve essere un nodo eccezionale di G. Ma allora C è una porzione eccezionale.

Sia allora C una A-porzione comune. Deve avere almeno due nodi. Per costruzione, C è un sottografo connesso. Mi rimane da verificare che tutti i suoi vertici tranne al più uno sono comuni (rispetto al grafo C).

Per il lemma di struttura, sappiamo che c'è un unico arco che congiunge A a C. Chiamo B il secondo estremo di tale arco. B potrebbe anche essere eccezionale nel sottografo C, ma dico che tutti gli altri nodi di C sono comuni.

Sia allora X un vertice di C distinto da B. Sappiamo che X non è connesso ad A e che è contenuto in una A-porzione comune. Significa che X è un nodo comune del grafo G.

Ma allora cancellandolo, deve disconnettere G. In particolare, esiste un nodo D [necessariamente distinto da A, B, X] che non è raggiungibile a partire da B lungo archi di G senza passare da X.

D deve essere un nodo di C. Se non lo fosse, esso sarebbe contenuto in una qualche A-porzione distinta da C. Ma allora esiste un percorso che va da B, su A, sulla A-porzione di D, a D. Ovviamente tale percorso non passa da X, dato che X sta in C. Ciò è in contrasto con il modo in cui ho scelto D.

Perciò B e D sono nodi di C. Se non è possibile andare da B a D senza passare da X lungo G, a maggior ragione ciò sarà vero lungo il sottografo C, dato che i percorsi possibili nel sottografo sono un sottoinsieme di tutti i percorsi nel grafo più grande.

Ne segue che cancellando X, C si disconnette e X è un nodo comune del grafo C. []

A questo punto la dimostrazione del claim è immediata: se esiste un grafo q.p.c., allora ne esiste anche uno minimale. Esso ha almeno un nodo comune A. A è di grado almeno 2 e quindi le A-porzioni sono almeno 2. Al massimo una di esse può essere eccezionale, quindi esiste una A-porzione comune.

Tale porzione risulta essere un grafo q.p.c. che ha strettamente meno vertici di G. Ma allora G non era minimale. Ne segue che non può esistere un grafo q.p.c. minimale e quindi nessun grafo q.p.c. affatto. []

Ciao. M.