grafi piani - un classico

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

grafi piani - un classico

Messaggio da ma_go » 12 nov 2012, 15:37

definizione (valida per questo thread). un grafo planare è un insieme finito di punti, detti vertici nel piano, collegati da una serie di archi "fatti bene", a due a due disgiunti (fatta eccezione per gli estremi), detti lati. ciascun arco collega tra loro due vertici distinti.

se preferite una definizione leggermente più precisa, mi sa che vi tocca usare il teorema di kuratowski, e dire che un grafo planare è un grafo che non contiene nessun sottografo che sia una suddivisione di $K_{3,3}$ o $K_5$.
ma sto divagando.

beh, adesso veniamo al problema:
problema. dimostrare che un grafo planare con $n$ vertici ha al più $3n$ lati.

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: grafi piani - un classico

Messaggio da Ido Bovski » 17 nov 2012, 00:01

Perché fermarsi a $3n$ lati? Non è difficile dimostrare che se $n\ge 3$ allora i lati sono al più $3n-6$.
Vabè, lascio un hint.
Testo nascosto:
Considera il grafo planare $G$ con $n$ vertici al quale non puoi aggiungere un nuovo lato per formare un grafo planare $G'\subsetneq G$ con $n$ vertici. Ogni faccia di $G$ è delimitata da $3$ lati.

matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Re: grafi piani - un classico

Messaggio da matty96 » 13 giu 2013, 21:50

Allora, ho studiato un pò di teoria dei grafi, vediamo se ho capito bene...
Sfrutto il fatto che un grafo è massimamente planare sse il bordo delle facce è triangolare, poichè se è triangolare avendo i tre vertici che sono connessi, non può esistere un altro lato che ne congiunge due , quindi se esistesse dovrebbe avere i due vertici sul bordo, ma ciò non è accettabile per la definizine di grafo piano.Contrariamente se è massimamente planare allora possiamo supporre di avere almeno quattro vertici che fanno parte del bordo, allora esiste un altro lato (quello tra 2 vertici non adiacenti) che lo separa e dunque si controddirebbe il "massimamente" (Siccome in questo caso esiste V(G')= V(G)). Dunque detto ciò notiamo che i primi tre vertici formano un triangolo, ma andando avanti posso scegliere un vertice che mi determina altri due triangoli con 3 lati distinti, quindi condati i tre lati formati dall'unione dei tre vertici iniziali, per ogni altro successivo avrò altri 3 lati...ergo si traduce in $3(n-3)+3=3n-6=l$ dove per l si intende ovviamente il numero dei lati
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $

matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Re: grafi piani - un classico

Messaggio da matty96 » 15 giu 2013, 16:08

Siccome stiamo parlando di grafi voglio chiarire una cosa...
Devo dimostrare che $T$ è un albero sse $T$ è minimamente connesso.
Se T è un albero suppongo falsa la connessione minima, quindi deve esistere un lato $e=uv$ tale da mantenermi $T$ ancora connesso. Ora sappiamo che se T è un albero, esiste un solo cammino tra due vertici, quindi anche per u-v, e siccome rimuovendo $e$ rimuovo anche questo cammino, si cade in contraddizione.
Se, invece, $T$ è minimamente connesso, suppongo che non sia un albero. Allora all'inetrno di $T$ esisterà un ciclo.Togliendo un lato $e$ dal ciclo, questo rimane comunque connesso perchè i vertici $u,v$ di $e$ saranno connessi ai lati adiacenti ad esso (e so che esistono perchè è un ciclo). Da ciò sto contraddicendo la minimalità.

Vorrei sapere se la soluzione è giusta, e se va bene scritta in questo modo.
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $

Avatar utente
phi
Moderatore
Messaggi: 349
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Re: grafi piani - un classico

Messaggio da phi » 16 giu 2013, 12:22

Visto che chiedi commenti sia sulla correttezza che sulla "forma", ti dico le mie impressioni. La soluzione sarebbe corretta, se non fosse per questa frase
matty96 ha scritto:Togliendo un lato e dal ciclo, questo rimane comunque connesso perchè i vertici u,v di e saranno connessi ai lati adiacenti ad esso (e so che esistono perchè è un ciclo)
che almeno a me non è chiara. Dato che il passaggio non è difficile, immagino che avessi in mente un argomento corretto, ma andrebbe spiegato meglio: quello che devi mostrare è che, dati due vertici qualunque, essi sono connessi anche una volta eliminato $e$; supponi che $e$ sia il lato $x_1x_2$ di un ciclo $x_1x_2\ldots x_nx_1$. Tu sai che, dati due vertici, nel grafo originario esiste un cammino $P$ che conduce dall'uno all'altro: se $P$ non contiene $e$, sei a posto; se $P$ contiene $e$, puoi sostituire $e$ con il cammino $x_2\ldots x_n x_1$ ottenendo un cammino che congiunge i vertici nel grafo privato di $e$.
Trovo che questo piccolo passaggio sia il più difficile della dimostrazione, perciò ti consiglierei di concedergli un minimo di spazio.

Secondariamente, una cosa che mi sentirei di consigliarti (in generale) è definire i termini che usi; in combinatoria (purtroppo!) la terminologia non è così standard, e ad esempio, anche se è chiaro che per "minimamente connesso" intendi "tale che esista un arco eliminando il quale il grafo non sia più connesso", dichiararlo non è mai una cattiva idea; questo anche per chiarirti le idee su quale definizione tu stia usando quando ce ne sono di equivalenti, e per essere certo - specialmente in esercizi su proprietà di base che vanno pericolosamente vicine alle definizioni degli oggetti in gioco - di non stare mescolando ipotesi e tesi.

Per quanto riguarda la tua soluzione al problema di ma_go, lì sono ben più perplessa. Tratti il fatto di non poter aggiungere archi alla tua triangolazione mantenendo la planarità come ovvio, ma disgraziatamente non lo è, anzi. Chiaro che non puoi aggiungere un arco fra due vertici della stessa faccia, ma chi ti dice che tu non possa farlo fra due vertici generici? Cos'è il bordo? Tieni presente che anche la faccia esterna, quella infinita, dev'essere triangolare, e quindi trattata alla stregua di qualunque altra, o tutto quello che dici è falso. Bisognerebbe dimostrare che, aggiungendo un arco fra vertici appartenenti a facce diverse non esiste nessun modo di realizzare il grafo come planare, neanche spostando liberamente i vertici, il che è ben difficile da stabilire se non mostrando esplicitamente l'esistenza di suddivisioni di $K_{3,3}$ o $K_5$ (cosa che, se fossi in te, non avrei nessun desiderio di fare).
In conclusione, l'hint era molto rischioso; se puoi evitare di dover dimostrare che un grafo astratto è o non è planare, beh, io eviterei. In effetti io dimostrerei il contenuto dell'hint (che è vero!) a partire dalla tesi di ma_go, anche se non dubito si possa fare senza. Dato che hai studiato un po' di teoria dei grafi, saprai che esistono strumenti utili proprio per non mettersi in situazioni scomode come quella dell'hint per dimostrare una disuguaglianza! :)
Testo nascosto:
Qual è LA formula che ti mette in relazione le quantità che t'interessano sui grafi planari...?

matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Re: grafi piani - un classico

Messaggio da matty96 » 16 giu 2013, 20:43

Innanzitutto ti ringrazio moltissimo per avermi dato abbastanza "una dritta" e ora vediamo un pò di rendere le cose più chiare. :D
Allora, ti dico già che sul file di teoria dei grafi questa proprietà viene già mostrata, però sapendo del problema qui proposto ho cercato di non leggerla o per lo meno di trovare qualche altra idea di soluzione.Infatti è li che avevo letto il teorema da cui ero partito, che mi sembra poi la vera parte della dimostrazione. Mi sono espresso male non definendo il bordo, perchè ho usato il linguaggio del file...comunque intendo la forma della faccia, nel senso che congiungendo tre vertici con i relativi lati ottengo un bordo triangolare. Sostanzialmente voglio dimostrare che se un grafo è massimamente planare, cioè è planare ma se aggiungo un lato non lo è più, allora il bordo di ogni faccia è triangolare. Ora se questo fosse falso(cioè il bordo non è triangolare, dunque ha più di tre vertici) il mio grafo planare, sarebbe costituito da facce con almeno quattro vertici, che sono connessi in modo tale da formare un quadrato o comunque una figura con almeno quattro lati, ma io posso connettere comunque altri due vertici non adiacenti (supponiamo un quadrato con vertici $v_1,v_2,v_3,v4$ e lati $v_1v_2,v_2v_3,v_3v_4,v_4v_1$ io posso in questo modo connettere anche $v_1 e v_3$ e il grafo rimane comunque planare perchè i lati non si intersecano), quindi sto aggiungendo un altro lato e questo dovrebbe essere impossibile per quel "massimamente" che abbiamo definito. Al contrario se portiamo dal fatto che il grafo abbia le facce triangolari (non penso che stiamo considerando pure quella esterna, perchè siccome è il "piano senza il grafo" non ha bordo definito) possiamo suppore falsa la massimalità planare e dobbiamo in qualche modo, però, sfruttare questa caratteristica e cioè in un qualche modo devo connettere un due vertici con un altro lato in modo tale che il grafo rimanga connesso (e ovviamente devo dimostrare che questo è impossibile). Se stiamo parlando della stessa faccia allora è impossibile perchè i vertici sono connessi in tutti i modi possibili (3 vertici $\binom{3}{2}=3$ lati), se stiamo parlando di due facce diverse allora il lato passerebbe comunque all'interno di una faccia e tocchetebbe un altro lato in suo punto per questo non può essere planare (è qua che mi sorge il dubbio). Alla fine considerato questo posso sfruttare la formula di eulero considerando che ogni lato appartiene a 2 triangoli adiacenti.Ma evevo trovato un altro modo: cioè prendo i primi 3 vertici li unisco e formo un triangolo, con il vertice successivo posso unire al massimo quegli stessi vertici, la stessa cosa per il successivo (questo perchè il quarto vertice è all'interno del grafo quindi non lo posso connettere) e cosi via... alla fine conterò 3 lati per i primi vertici e 3 per ciascuno degli $n-3$ cioè $3+3(n-3)=3n-6$ lati.
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $

Avatar utente
phi
Moderatore
Messaggi: 349
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Re: grafi piani - un classico

Messaggio da phi » 16 giu 2013, 22:52

Mmmmh.
Non c'era alcun dubbio che la parte "se non tutte le facce sono triangolari, allora il grafo non è massimamente planare" fosse corretta (anche se, ti ripeto, la faccia esterna conta; anche solo per fartene un'idea, considera il numero di archi di un quadrato con una diagonale: 5, per 4 vertici, mentre 3*4-6=6; unisci due vertici non adiacenti del quadrato con un arco che passi per la faccia esterna e avrai un grafo davvero massimamente planare, che ha in effetti 6 archi, e in cui anche la faccia esterna è triangolare).
Ad ogni modo quello che mi premeva sottolineare è che l'altra faccia non funziona, continua a non farlo, e difficilmente comincerà a farlo mantenendo lo stesso approccio di dimostrazione: questo perché non è sufficiente disegnare un arco in un certo modo su un grafo planare già disegnato nel piano e rendersi conto che intersecherebbe altri archi, per dimostrare che il nuovo grafo non è planare. Prendi il quadrato con una diagonale, e disegna l'altra diagonale: il grafo che ottieni è planare, seppure non disegnato in modo planare; basta spostare una delle due diagonali fuori dal quadrato per rendere il fatto lampante. Per cui non basta dire che, con il grafo disegnato in un certo modo, aggiungere un segmento fra due vertici rende il disegno non planare, per concludere che il grafo iniziale era massimamente planare. Un ragionamento funzionante per questa freccia non è facile da produrre, e il mio hint era inteso nell'ottica di partire da zero, senza dimostrare nessun lemma di massimale planarità, e impostando il tutto in maniera piuttosto diversa.

matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Re: grafi piani - un classico

Messaggio da matty96 » 16 giu 2013, 23:51

E infatti era proprio questa la cosa che non mi quadrava, perchè sapevo dell'esistenza del quadrato con le due diagonali unite ma che rimaneva piano. Ripensandoci però credo di aver inserito un fatto in più nella dimostrazione che credo si possa omettere (e se è cosi allora è tutta colpa della mia volontà a consultare la dispensa!). Pensando all'hint di Ido, che sostanzialmente dice :"se G è massimamente planare allora ha le facce triangolari" e che io ho dimostrato, non c'è bisogno di dimostrare il contrario perchè se G è massimamente planare allora non può esistere un altro grafo G' di n vertici planare con un numero di lati maggiore di G. Infatti se G' non è massimamente planare allora posso aggiungere un lato che mi mantenga il grafo planare e a questo punto o è massimamente planare o posso continuare ad aggiungere, ad ogni modo ne avrò sempre uno con più lati di G'. Quindi siccome io voglio sapere quanti lati può avere al massimo una grafo planare, considero quello massimale. Dimostrato che ha le facce triangolari ho che ogni lato appartiene a due facce adiacenti, quinti se conto il numero dei lati faccia per faccia, avrò che sto contando due volte i lati...allora $3f=2m$ , $f=\frac{2}{3}m$ sostituendo nella formula di eulero ho $n+\frac{2}{3}m=m+2$, cioè $m=3n-6$
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $

fph
Site Admin
Messaggi: 3659
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: grafi piani - un classico

Messaggio da fph » 17 giu 2013, 00:08

Volendo essere fiscali, dovresti anche dimostrare che non è possibile aggiungere archi all'infinito, ma che prima o poi ti fermi. E, sempre sul fiscaloide, non scrivere "quello massimale", perché non ce n'è uno solo. :)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Re: grafi piani - un classico

Messaggio da matty96 » 17 giu 2013, 00:30

Beh,considerando che per n vertici ho al massimo $n(n-1)/2$ lati...il fatto che prima o poi finisca è scontato( considerando grafi semplici).
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $

fph
Site Admin
Messaggi: 3659
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: grafi piani - un classico

Messaggio da fph » 17 giu 2013, 10:11

matty96 ha scritto:Beh,considerando che per n vertici ho al massimo $n(n-1)/2$ lati...il fatto che prima o poi finisca è scontato.
Giusto, giusto. Non stavo dicendo che era difficile / complicato, solo che per fare una dimostrazione a prova di bomba andrebbe scritto. Ci sono un sacco di casi simili in cui un ragionamento del genere non funziona proprio perché si può andare avanti all'infinito, ergo è un punto delicato.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
phi
Moderatore
Messaggi: 349
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Re: grafi piani - un classico

Messaggio da phi » 17 giu 2013, 11:28

E' vero, adesso dovrebbe funzionare tutto :)
Giusto come esercizio, puoi provare a farlo eliminando anche quella freccia, usando solo il fatto che ciascuna faccia ha almeno tre lati, e in questo modo la stesura è un po' più rapida e non sfiora questioni delicate come quelle che ti ha fatto notare fph. Adesso hai anche l'altra freccia "gratis", una volta mostrata la disuguaglianza, sei d'accordo? Se aggiungi un arco a un grafo planare con tutte le facce triangolari, hai semplicemente troppi archi perché sia mantenuta la planarità (insomma: si finisce per risolvere il problema di ma_go prima di poter mostrare l'altra freccia). E, in generale, un conteggio di archi è un ottimo modo per dimostrare la non planarità di un grafo; per questo il lemma di ma_go (o, ancora meglio, il risultato leggermente più forte che hai mostrato tu) può rivelarsi utile in tante situazioni.

Rispondi