k5 non è planare

[EvaristeG]

Da un problema di geometria ecco un pezzo di teoria dei grafi.
La realizzazione planare di un grafo G è un insieme di punti e linee tra essi che corrisponde nel modo sensato ai vertici e ai lati di G, di modo che i lati si intersechino solo nei loro estremi che sono tutti vertici.
Un grafo è planare se ha una realizzazione planare (insomma, se si può disegnare nel piano).
Supponiamo che G sia connesso.
Supponiamo di aver dimostrato che ogni rappresentazione planare di un grafo finito divide il piano in un certo numero di "pezzi", che sono le facce della rappresentazione.

Allora
1)$ v-e+f=2 $, dove v è il numero di vertici, e è il numero di lati, f è il numero di facce
2)$ e\leq 3v-6 $ se $ v\geq 3 $
3) G non può avere 5 vertici e 10 lati.

Quindi G non può essere il grafo completo con 5 vertici (ovvero quello in cui ogni vertice è collegato a tutti gli altri).

Nota Bene : non è roba difficile, quindi ...

[antosecret]

Supponiamo che G sia connesso.
Supponiamo di aver dimostrato che ogni rappresentazione planare di un grafo finito divide il piano in un certo numero di "pezzi", che sono le facce della rappresentazione.

1)$ v-e+f=2 $, dove v è il numero di vertici, e è il numero di lati, f è il numero di facce

Sperando di non scrivere stupidaggini e di non applicare male l'induzione....

Allora....
Passo base: Per un grafo con un solo vertice, v-e+f = 1-0+1=2 OK

Passo induttivo: Dato un certo grafo G per cui vale la tesi, essa varrà anche per un qualunque altro grafo derivato da G aggiungendo:

1) 1 vertice che divide un lato in 2: infatti in questo modo aumentano di 1 sia i vertici che i lati e quindi la tesi vale lo stesso $ [tex] $(v+1)-(e+1)+f = v-e+f=2[\tex]

2) un lato che collega 2 vertici: in questo caso, poichè il grafo è planare, aggiungerò al grafo iniziale un nuovo lato e formerò una nuova faccia.... e la relazione vale lo steso.

3) un vertice e un lato che lo collega a un vertice del grafo: in questo caso aggiungo 1 nuovo vertice e 1 nuovo lato, ma non si forma nessuna nuova faccia quindi la relazione vale anche qua.

Non posso aggiungere al grafo ne un vertice ne un lato isolati poichè il grafo deve essere connesso.

Allora, poichè partendo dal grafo più semplice (1 solo punto) e ingrandendo il grafo in ogni modo possibile la relazione resta comunque valida, la relazione sarà valida per ogni grafo che soddisfa le ipotesi.
------

Che ve ne pare???? E' giusta?
In particolare sono perplesso sul fatto che così sto considerando tutti i grafi possibili (altrimenti l'induzione non varrebbe....)

[Oblomov]

Se è possibile mi permetto di rilanciare: mi sembra che in effetti gli unici grafi non planari siano il già citato "grafo-5" (cinque vertici, ognuno collegato a tutti gli altri) e quello che potremmo chiamare "grafo-3/3" , cioè il grafo i cui vertici possono essere suddivisi in due gruppi A e B (di tre vertici cadauno) tali che ogni elemento di A sia collegato a ogni elemento di B (nient'altro che il classico problemino delle tre case da allacciare per acqua, luce e gas)... questi grafi appunto, oltre ovviamente ai grafi che "contengono" almeno uno di questi due.
E' vero? E' (umanamente) dimostrabile?
Fatemi sapere.

Buonanotte a tutti
Ob

[EvaristeG]

Ob, è vero ... se volete posto anche il conteggio che serve per K3,3.
Così si dimostra che questi due non stanno nel piano ... con un po' di fiducia, si dimostra anche che tutti quelli che permettono di ottenere uno dei due per contrazioni non stanno nel piano.
Dimostrare che così ho descritto tutti i grafi non planari ... beh, è un po' più complicato.

PS: antosecret, le induzioni si fanno o aggiungendo qualcosa al caso n per ottenere il caso n+1 o togliendo qualcosa al caso n+1 per avere il caso n ... in questo caso tu aggiungi, ma il problema, come giustamente noti, è che ti rimane da dimostrare che così puoi ottenere tutti i grafi.
Qui è più "pulito", secondo me, cercare di prendere il caso n+1 e togliere qualcosa ... se vuoi pensarci, fallo. Altrimenti, leggi l'hint.

se G è un albero (non ha cicli) la formula si dimostra a parte, altrimenti si può togliere un lato in un ciclo...

[pa]

provo il punto due (anche se non so se la dimostrazione e' molto rigorosa...).
induzione: poniamo di avere un grafo planare di n nodi disegnato sul piano e che abbia un numero massimo di archi. il caso base per n=3 e' semplicemente un triangolo e la formula e' verificata.
Ora ogni faccia di questa grafo (quello con n nodi non il caso base) non puo' avere piu' di 3 lati, infatti se ne avesse di piu' sarebbe possibile tracciare un arco da due nodi non adiacenti ottenendo un grafo planare con piu' archi contraddicendo l'ipotesi. Vale anche per la faccia esterna al grafo.
Posso ottenere un grafo di n+1 nodi con un numero massimo di archi (forse questo passaggio e' un po' debole) oggiungendo un nodo in mezzo a una faccia del grafo precedente e congiungendolo con vertici della faccia. Cosi' facendo oggiungo un nodo e 3 archi e la formula e' quindi ancora valida.
Il punto tre e' una conseguenza del punto due perche' se una parte del grafo non puo' essere disegnata su un piano e' evidente che tutto il grafo non puo' essere disegnato su un piano.

[antosecret]

in questo caso tu aggiungi, ma il problema, come giustamente noti, è che ti rimane da dimostrare che così puoi ottenere tutti i grafi.[/color]

[/quote]

Riguardando bene (ricordavo di aver già visto questa dimostrazione tempo fa) i miei appunti ho trovato questa dimostrazione: l'avevo già fatta allo stage junior del 2006 come dimostrazione della validità di un invariante (in questo caso la legge di eulero)....
Alla fine si dava per buono che ripetendo il procedimento all'infinito era possibile ottenere qualunqua grafo....
In realtà a me sembra abbastanza intuitivo che così si possano ottenere tutti i grafi possibili (in fin dai conti un grafo non è che una somma di "mattoncini", quindi avendo a disposizione i mattoncini più piccoli possibili si dovrebbe poter costruire qualunque "costruzione"....)

Se ad esempio facessi una cosa del genere a cesenatico me la darebbero per buona?????

[EvaristeG]

"se è ovvio e intuitivo, che problema ti fa spiegarmelo?"
a parte la frase polemica, no, una cosa del genere non va bene: devi in qualche modo giustificare il fatto che tutti i grafi vengano costruiti ... "si vede" è una motivazione un po' instabile.
Come ho detto, la cosa più facile è cercare di togliere: partire da un grafo in qualche senso più grande e usare che la tesi è supposta vera per i grafi più piccoli che si ottengono da lui in qualche modo.

[Tibor Gallai]

Se ad esempio facessi una cosa del genere a cesenatico me la darebbero per buona?????

Scritta come l'hai scritta, probabilmente no. Non hai dimostrato che con quella costruzione ottieni tutti i grafi.
Chi è stato a dimostrartelo in quel modo allo stage? Forse hai scritto male gli appunti, non posso credere che qualcuno ti abbia detto quella cosa.

[antosecret]

Se ad esempio facessi una cosa del genere a cesenatico me la darebbero per buona?????

Scritta come l'hai scritta, probabilmente no. Non hai dimostrato che con quella costruzione ottieni tutti i grafi.
Chi è stato a dimostrartelo in quel modo allo stage? Forse hai scritto male gli appunti, non posso credere che qualcuno ti abbia detto quella cosa.

E' possibile che io abbia sbagliato a scrivere i miei appunti anche se lo credo improbabile.....

Purtroppo non ricordo il nome del professore...
Era quello che ha fatto la prima lezione (trucchi o preliminari) dello stage junior di napoli del 2006.....

Quale potrebbe essere un modo di dimostrare che con quella costruzione si ottengono tutti i grafi possibili????

[EvaristeG]

pa, c'è lo stesso problema della dimostrazione di antosecret .. devi dimostrare che così ottieni tutti i grafi di n+1 vertici con un numero massimo di lati...
cmq, se l'ho messo come punto due, evidentemente si usa il punto uno.
Per il punto 3 non ho capito cosa hai detto: non è una parte del grafo che non si può disegnare ... è proprio tutto lui, infatti 10 è maggiore di 3*5-6 ... anzi, ogni grafo ottenuto da lui togliendo un lato rispetta quella formula.

[EvaristeG]

E' abbastanza ininfluente chi è stato.
Comunque, la dimostrazione che con quella costruzione si ottengono tutti i grafi si fa ovviamente prendendone uno che si vuole ottenere e togliendo qualcosa con una mossa opposta a una delle tue, dimostrando che si ottiene così un grafo più piccolo che si sapeva già costruire. Ovvero sia, si dimostra rifacendo questa stessa dimostrazione come ti ho detto io...

[antosecret]

E allora ci riprovo...

Passo base: come prima

Passo induttivo: supponiamo di avere un qualunque grafo G, da cui sappiamo che rimuovendo un lato o un vertice otteniamo un nuovo grafo più piccolo per cui vale la tesi. Allora anche per il grafo G la tesi è verificata.

In particolare possiamo distinguere 2 casi:
1) è possibile togliere 1 lato del grafo ottenendo ancora un grafo connesso...
In questo caso togliendo un lato qualunque (essendo il grafo planare) non faccio altro che eliminare una faccia. Quindi la relazione vale lo stesso

2) Non è possibile togliere 1 lato del grafo ottenendo ancora un grafo connesso...
Allora ci sarà almeno un vertice da cui parte un solo lato (Infatti se da ogni vertice partissero almeno 2 lati sarebbe possibile, scegliendo un vertice a caso, muoversi all'infinito e quindi fare necessariamente un ciclo, supposto il grafo finito). Basterà allora rimuovere questo lato e questo vertice per ottenere ancora un grafo per cui vale la tesi (rimuoviamo quindi un lato e un vertice, non rimuoviamo nessuna faccia e la tesi resta verificata....)

Così va meglio????? A me sembra un poco la stessa cosa di prima riscritta in un altro modo....

[EvaristeG]

E' la stessa cosa nel senso che questa giustifica quella di prima: quella di prima senza questa non ha molto senso.
Comunque, ora rimane il punto 2.
Chi lo fa?
La soluzione di pa aveva lo stesso vizio di quella di antosecret prima della revisione: fa l'induzione nella direzione sbagliata. Chi dice che aggiungendo punti come fa lui si ottengono da grafi di n vertici con numero massimo di archi TUTTI i grafi di n+1 vertici con numero massimo di lati?

[antosecret]

Io sono arrivato a riformulare la tesi come $ 3f\le2e $ sostituendo alla tesi la formula di eulero....

Domani continuo a provarci...

[EvaristeG]

Ecco, ora devi trovare una relazione tra lati e facce, per poterli contare entrambi.