Grafi

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Grafi

Messaggio da Marco »

enomis_costa88 ha scritto:dov'è che posso trovare una bella dispensa sui grafi??
Ciao. Sul "bella" non mi pronuncio. Nel week-end ho buttato giù questa. Spero non contenga troppe inesattezze...

Definizioni:

Di un grafo possiamo dare due definizioni: una più intuitiva e grafica, l'altra più precisa e insiemistica.

Un grafo è un insieme di punti (detti vertici oppure nodi) e di archi (oppure spigoli o anche lati) che hanno gli estremi nei vertici.

Ci sono alcune regolette che questi archi devono soddisfare:

- gli estremi di un arco sono su vertici distinti (salvo che non sia esplicitamente consentito il contrario)

- se un arco congiunge X con Y, nessun altro arco congiunge X con Y (altrimenti si parla di multigrafo

In un grafo non conta la topografia, ma la combinatoria, quindi non è importante sapere se le righe degli archi sono dritte o storte, si intersecano o no. E' invece importante sapere chi è collegato con chi.

Questo suggerisce la definizione insiemistica:

Un grafo è un insieme V di vertici e un insieme A, con la proprietà che gli elementi di A sono sottoinsiemi di due elementi di V (=coppie non ordinate di V).

A è l'insieme degli archi: un arco (grafico) è tracciato tra i vertici X e Y sse la corrispondente coppia {X,Y} (arco insiemistico) appartiene ad A.

Notate che in questo modo garantite automaticamente le due regolette degli archi. Nel seguito non sarà importante quale delle due rappresentazioni (grafica o insiemistica) scegliete. Normalmente alcuni concetti sono più intuitivi se vi fate un disegno.

-----------------------------------

Terminologia:

Un grafo è finito se ha un numero finito di vertici. Nel seguito supporrò sempre i grafi finiti.

Dato un grafo un suo sottografo è ottenuto cancellando alcuni (eventualmente nessuno) archi e alcuni (ev. nessuno) vertici, in modo che l'oggetto ottenuto sia ancora un grafo (e quindi, ad esempio, non si cancelli un nodo se ci sono degli archi che vi giungono).

Se in un grafo è possibile, camminando lungo gli archi, andare da X a Y, comunque si scelgano X e Y tra i nodi del grafo, si dice che il grafo è connesso.

Dato un vertice, l'insieme dei nodi raggiungibili dal vertice dato seguendo gli archi è detto componente connessa.

Il numero di archi che si dipartono da un nodo è detto grado del vertice. Un vertice di grado 0 è detto punto (nodo, vertice) isolato ed è sempre anche una componente connessa.

Un grafo è detto completo se contiene il massimo numero possibile di spigoli. Cioè, se per ogni coppia di vertici c'è un arco che li congiunge.

Un grafo è detto bipartito se è possibile colorare in rosso e blu i suoi vertici in modo tale che ogni arco abbia gli estremi di colori diversi. Un grafo è bipartito completo se contiene un arco per ogni coppia di vertici con colori diversi. Attenzione che la terminologia è ambigua e dicendo "bipartito" il più delle volte si sottintende "bipartito completo"!

Analogamente un grafo tripartito, quadripartito, ecc..., anche se si incontrano decisamente molto più di rado.

Dati due vertici nella stessa componente connessa, è possibile definire la distanza tra loro come il minimo numero di archi che occorre percorrere per andare da uno all'altro. La massima distanza possibile è detta diametro.

Un percorso lungo gli archi che consenta senza ripercorrere uno stesso spigolo più di una volta di tornare al punto di partenza è detto ciclo. Un grafo senza cicli è detto aciclico e, se è anche connesso, è detto albero

Se in un albero fissiamo un vertice particolare (che chiameremo radice). La distanza dalla radice è detto livello. Il livello massimo dei suoi nodi è detto altezza.

I vertici di grado 1 diversi dalla radice sono detti foglie. I vertici che non sono né radice, né foglie sono detti nodi intermedi (attenzione: spesso si sottintende "intermedio", con la possibilità di confondersi con l'altro significato di nodo come vertice generico; normalmente il contesto chiarisce).

Se tutti i nodi hanno grado 3 l'albero è detto binario. Se tutti i nodi hanno grado quattro è detto ternario, ecc...

Se è possibile disporre vertici e archi su un piano in modo tale che gli archi non si intersechino, il grafo è detto planare. [Nota di folklore: c'è un teorema non banale che dice che i vertici di un grafo planare possono essere disposti sul piano in modo che gli archi siano segmenti non intersecantisi.]

Se abbiamo un grafo planare, ognuna delle regioni in cui il piano è diviso è detta faccia. Notare bene: anche la regione illimitata è una faccia.

-----------------------------------

Esercizi

Dimostrare che ogni grafo ha un numero pari di vertici di grado dispari.

Dimostrare che: le componenti connesse sono sottografi connessi che costituiscono una partizione del grafo; essere nella stessa componente connessa è una relazione di equivalenza.

Quanti archi ha il grafo completo con n vertici? Quanto vale il grado di ogni suo vertice? Quanto vale il suo diametro?

Quanti archi ha un grafo bipartito [completo] con m vertici blu e n vertici rossi? Quanto vale il grado di ogni suo vertice? Quanto vale il suo diametro?

Supponiamo che un grafo abbia v vertici, tutti con lo stesso grado d e s spigoli. Trovare una formula che leghi d, v e s.

Dimostrare che la distanza è proprio una distanza, ossia che d(X,X) = 0, d(X,Y)=d(Y,X) e che vale la diseguaglianza triangolare d(X,Y) + d(Y,Z) >= d(X,Z).

Calcolare il numero di archi di un grafo aciclico, in funzione dei vertici e delle cp.ti cn.se.

Dimostrare che in un albero i nodi di livello massimo sono foglie. E' vero il viceversa?

Dimostrare che ogni nodo ha un unico arco che lo congiunge ad un nodo di livello inferiore. Usare questo fatto per dimostrare che il percorso che congiunge ogni vertice alla radice è unico; che dati due qualunque vertici, il percorso che li congiunge è unico.

In un albero si sa che la radice ha grado r, le foglie sono tutte al livello h e i nodi intermedi hanno tutti grado d. Calcolare il numero di foglie e il numero totale di vertici.

[Formula di Eulero] Se un grafo planare connesso ha F facce, V vertici e S spigoli, allora

F + V = S + 2
["Fatti Vedere Sabato alle Due": Facce + Vertici = Spigoli + 2]

Dimostrare che il grafo completo con 5 vertici e il grafo bipartito (3,3) non sono planari. Dimostrare che un qualunque grafo bipartito (n,2) è planare.

Dimostrare che un albero è un grafo planare.

[Numeri di Ramsey] Se coloriamo gli archi di un grafo completo con 6 vertici in rosso o blu, allora esiste un triangolo monocromatico. Dimostrare che 6 è il minimo possibile. Dimostrare che se coloriamo gli archi di un grafo completo con 17 vertici in rosso, blu o verde, allora esiste un triangolo monocromatico. Dimostrare che 17 è il minimo possibile.

[Ponti di Koenigsberg; Criterio di Eulero] E' possibile disegnare un grafo senza mai staccare la matita dal foglio se e solo se
- è connesso
- possiede al massimo 2 vertici di grado dispari.

Nel caso che abbia esattamente due vertici di grado dispari, dove si trovano gli estremi del percorso?
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
Melkon
Messaggi: 259
Iscritto il: 01 gen 1970, 01:00
Località: Ferrara

Messaggio da Melkon »

Dimostrare che ogni grafo ha un numero pari di vertici di grado dispari.
facciamolo per induzione (credo) partendo da un grafo finito senza archi. il grafo ha 0 (pari?) vertici di grado dispari, infatti sono tutti di grado 0 (ancora, pari?).
Se tracciamo un vertice possiamo congiungere solo due componenti di grado P, che diventeranno entrambe D. Ora possiamo congiungere vertici:
P con D (che non cambia la parità di vertici di grado dispari)
P con P (idem)
ed eventualmente anche
D con D (idem)
andando avanti nella nostra furia grafoclasta. Le mosse consentite però mantengono un numero pari di vertici di grado dispari, proprietà quindi di tutti i grafi [].
"Bisogna vivere come si pensa, se no, prima o poi, ci si troverà a pensare come si è vissuto"
Paul Borget
Avatar utente
Melkon
Messaggi: 259
Iscritto il: 01 gen 1970, 01:00
Località: Ferrara

Messaggio da Melkon »

Quanti archi ha il grafo completo con n vertici? Quanto vale il grado di ogni suo vertice? Quanto vale il suo diametro?
disponiamo i vertici come vertici di un n-agono regolare
(sfruttando che le diagonali di un poligono sono n(n-3)/2 e quindi) gli archi di un grafo completo sono n(n-1)/2. Il grado di ogni vertice vale n-1 (togliamo se stesso ma è collegato con ogni altro vertice). Il diametro vale 1 perché se è il grafo è completo da ogni vertice si raggiunge ogni altro
"Bisogna vivere come si pensa, se no, prima o poi, ci si troverà a pensare come si è vissuto"
Paul Borget
Avatar utente
Melkon
Messaggi: 259
Iscritto il: 01 gen 1970, 01:00
Località: Ferrara

Messaggio da Melkon »

[Numeri di Ramsey] Se coloriamo gli archi di un grafo completo con 6 vertici in rosso o blu, allora esiste un triangolo monocromatico. Dimostrare che 6 è il minimo possibile.
forse mi sfugge qualcosa... con 5 vertici ce ne sono almeno 3 dello stesso colore, e il triangolo monocromatico è bell'e fatto...
"Bisogna vivere come si pensa, se no, prima o poi, ci si troverà a pensare come si è vissuto"
Paul Borget
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Melkon ha scritto:facciamolo per induzione (credo) partendo da un grafo finito senza archi. il grafo ha 0 (pari?) vertici di grado dispari, infatti sono tutti di grado 0 (ancora, pari?).
Se tracciamo un vertice possiamo congiungere solo due componenti di grado P [...]
Una volta e per tutte, zero è pari. Attento alla terminologia (mi sembra il minimo, dopo che ho sbrodolato cinque pagine di definizioni...): non si tratta di componenti, ma di vertici; non tracci vertici, ma spigoli. Per il resto, soluzione bruttina, ma valida.

Chi trova una dimostrazione più diretta, senza induzione, ma con un astuto double-counting?
Melkon ha scritto:con 5 vertici ce ne sono almeno 3 dello stesso colore, e il triangolo monocromatico è bell'e fatto...
Occhio! Non si colorano i vertici, bensì gli archi e se hai solo cinque vertici...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Re: Grafi

Messaggio da Boll »

Marco ha scritto:[Formula di Eulero] Se un grafo planare connesso ha F facce, V vertici e S spigoli, allora F + V = S + 2
Induzione su S, per S=1 banalmente vero. Se aggiungo un S per forza devo aggiungere anche un F (se collego ad un V) o un V (se mi "butto nel vuoto"). Il chè conclude la dimostrazione.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Grafi

Messaggio da fph »

Boll ha scritto:
Marco ha scritto:[Formula di Eulero] Se un grafo planare connesso ha F facce, V vertici e S spigoli, allora F + V = S + 2
Induzione su S, per S=1 banalmente vero. Se aggiungo un S per forza devo aggiungere anche un F (se collego ad un V) o un V (se mi "butto nel vuoto"). Il chè conclude la dimostrazione.
hmm... prova a formalizzare meglio questa dimostrazione. Secondo me si arriva a un "buchetto", a un certo punto. Vediamo se riesci a notarlo... (a meno che non mi sbagli io. Qualcun altro conferma? Era un "problemino" intrinseco delle dimostrazioni di questo tipo, se ne è parlato all'ultimo stage di Pisa)

ciao,
--f
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Mmmmh, forse perchè considero solo il caso in cui aggiungo uno spigolo che non taglia nessun altro spigolo???? E' questo?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

Boll ha scritto:Mmmmh, forse perchè considero solo il caso in cui aggiungo uno spigolo che non taglia nessun altro spigolo???? E' questo?
mmh... anche, probabilmente. E' un aspetto. Ma stai ancora guardando il problema "dal verso sbagliato", e' qualcosa a un livello piu' "di base".
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Hammond
Messaggi: 110
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da Hammond »

Marco ha scritto:Dimostrare che ogni grafo ha un numero pari di vertici di grado dispari.
Chiamiamo $ S $ la somma dei gradi di tutti i vertici.
Notiamo che $ S $ è pari, in quanto ogni arco viene contato esattamente due volte in $ S $, una per il vertice di partenza e una per quello di arrivo.
Se i vertici di grado dispari fossero in numero dispari, si arriverebbe all'assurdo che $ S $ è dispari; quindi sono in numero pari.
BlaisorBlade
Messaggi: 113
Iscritto il: 01 gen 1970, 01:00
Località: Catania

Re: Grafi

Messaggio da BlaisorBlade »

fph ha scritto:
Boll ha scritto:
Marco ha scritto:[Formula di Eulero] Se un grafo planare connesso ha F facce, V vertici e S spigoli, allora F + V = S + 2
Induzione su S, per S=1 banalmente vero. Se aggiungo un S per forza devo aggiungere anche un F (se collego ad un V) o un V (se mi "butto nel vuoto"). Il chè conclude la dimostrazione.
hmm... prova a formalizzare meglio questa dimostrazione. Secondo me si arriva a un "buchetto", a un certo punto. Vediamo se riesci a notarlo... (a meno che non mi sbagli io. Qualcun altro conferma? Era un "problemino" intrinseco delle dimostrazioni di questo tipo, se ne è parlato all'ultimo stage di Pisa)

ciao,
--f
Dunque, la dimostrazione che io avevo visto era più o meno questa, al massimo va formalizzata un po' meglio.

Se non sbaglio, il tipico problema delle dimostrazioni di questo tipo è che non tutti i "garbugli" validi con N elementi si ottengono da "garbugli" validi con N-1 elementi; parlo di "garbugli" perché il problema non è limitato ai grafi, e non vale sui grafi in generale... vale penso sui grafi in cui si vanno a imporre condizioni adatte.

Per esempio, che un grafo planare sia ottenibile da grafi planari è vero, ma che un grafo connesso sia riducibile, rimuovendo un arco e un vertice/faccia, a un'altro grafo connesso è molto meno banale: lo è, penso, scegliendo opportunamente l'arco da rimuovere, ma non mi sembra banale da dimostrare.

In ogni caso, la formalizzazione corretta non è per induzione, ma per regressione al caso base: preso un grafo qualunque, a furia di rimuovere elementi ci si riduce al grafo avente un solo vertice e senza archi, per cui la formula vale, e nel frattempo la formula è un invariante conservato dalle trasformazioni, purché il grafo resti connesso. Dimostriamo questo e abbiamo finito.
Avatar utente
Paoloca
Messaggi: 88
Iscritto il: 18 apr 2005, 18:11

Re: Grafi

Messaggio da Paoloca »

Marco ha scritto:
enomis_costa88 ha scritto:dov'è che posso trovare una bella dispensa sui grafi??
Ciao. Sul "bella" non mi pronuncio. Nel week-end ho buttato giù questa. Spero non contenga troppe inesattezze...

Grazie mille.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Grafi

Messaggio da fph »

BlaisorBlade ha scritto:
Boll ha scritto:
Marco ha scritto:[Formula di Eulero] Se un grafo planare connesso ha F facce, V vertici e S spigoli, allora F + V = S + 2
Induzione su S, per S=1 banalmente vero. Se aggiungo un S per forza devo aggiungere anche un F (se collego ad un V) o un V (se mi "butto nel vuoto"). Il chè conclude la dimostrazione.
Se non sbaglio, il tipico problema delle dimostrazioni di questo tipo è che non tutti i "garbugli" validi con N elementi si ottengono da "garbugli" validi con N-1 elementi; parlo di "garbugli" perché il problema non è limitato ai grafi, e non vale sui grafi in generale... vale penso sui grafi in cui si vanno a imporre condizioni adatte.
Centro :-D . Il problema e' che ci va almeno un po' di lavoro per dimostrare che da ogni grafo si può "togliere" un lato per bene. Altrimenti, se fai un'induzione "costruendo" invece che "distruggendo", rischi di non generare tutti i grafi planari ma solo una sotto-classe in cui la tua tesi è vera. Per esempio, prova a considerare cosa succede per i grafi sulla superficie di un toro (toro=una superficie a forma di "ciambella", per i matematici). Le due operazioni che hai indicato sono perfettamente valide ma generi solo un sottoinsieme di tutti i possibili grafi.

(consiglio per i problem-solver: domanda chiave per trovare "buchi" di questo tipo e' chiedersi: dove ho usato esattamente le ipotesi? le ho usate tutte? E, in generale, ricordate che le induzioni "distruggendo" funzionano meglio di quelle "costruendo".)

ciao,
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 »

Mi spiace per eventuali doppioni ma non ho ancora letto le altre soluzioni(e poi preferisco postarle tutte perchè con qualcuna ho avuto difficoltà a formalizzare o non ci sono riuscito per niente quindi si può correggere insieme..)

Dimostrare che ogni grafo ha un numero pari di vertici di grado dispari.
Chiamo A la somma dei gradi totali dei vertici che è pari perché ogni arco aumenta di uno il grado di due vertici. P = sum grado vertici pari;D = sum grado vertici dispari. P è pari perché somma di numeri pari; A-P=D ma A,P sono pari quindi anche D lo è. Ma D è somma di numeri dispari per cui gli addendi sono in numero pari.

Dimostrare che: le componenti connesse sono sottografi connessi che costituiscono una partizione del grafo; essere nella stessa componente connessa è una relazione di equivalenza.
Una componente connessa non può avere archi che la congiungono con vertici esterni perché se così fosse si potrebbe andare da A(interno) a B(esterno) che è falso per la definizione di componente connessa.
Non avendo archi in comune con l’esterno gli archi possono essere ripartiti in due insiemi(interni ed esterni) lo stesso si può fare per i nodi. Quindi è una partizione del grafo iniziale. Una componente connessa inoltre è un grafo: cancellando tutto ciò che è esterno se non risultasse un grafo (ovvero se ci fossero archi non terminanti in un nodo) vuol dire che nemmeno quello iniziale lo era perché i nodo connessi ad altri della componente sono interni e non sono stati cancellati. Essendo un grafo e partizione del grafo iniziale si può chiamare sottografo.
In una c.c. si può andare da un nodo A (per la definizione..) a qualsiasi altro nodo, quindi tutti i nodi sono connessi tra loro (passando per A si può andare dappertutto) quindi è un sottografo connesso.
In seguito si può usare la relazione di equivalenza dell’appartenere alla stessa partizione.
Proprietà riflessiva:Partizionando(interni esterni) i vertici A appartiene allo stessa partizione i A.
Simmetrica: (ancora partizionando) A appartiene alla stessa partizione di B quindi vale il simmetrico.
Transitiva: da A posso andare a B; da B posso andare a C quindi da A posso andare a C passando per B.

Quanti archi ha il grafo completo con n vertici? Quanto vale il grado di ogni suo vertice? Quanto vale il suo diametro?
Un grafo completo non può avere più archi del numero di coppie perché ci sarebbero min 2 coppie collegate due volte(supponendo che gli archi colleghino coppie come nella definizione di grafo) se avesse meno del numero di coppie ci sarebbero delle coppie non collegate direttamente e quindi potrebbero esserci altri archi e non si ha il numero max di archi. Quindi: $ { n \choose 2} = \frac{n(n-1)}{2} $
Ogni vertice è connesso direttamente ad altri n-1 da cui il grado.
1 è la distanza max tra due vertici perché data una coppia esiste l’arco che li connette.


Quanti archi ha un grafo bipartito [completo] con m vertici blu e n vertici rossi? Quanto vale il grado di ogni suo vertice? Quanto vale il suo diametro?
Ogni vertice blu si collega con n rossi; ogni rosso con m blu inoltre ogni arco collega due vertici quindi:
$ \frac {2mn}{2} = mn $ ; dall’affermazione di prima di ricava il grado cioè m per i rossi e n per i blu.
Il diametro è due perché se due vertici sono di colore diverso esiste un arco che li connette; se sono dello stesso colore vado da A ad un qualsiasi B di colore diverso dal quale posso andare in tutti i vertici del colore di A.


Supponiamo che un grafo abbia v vertici, tutti con lo stesso grado d e s spigoli. Trovare una formula che leghi d, v e s.
Dai v vertici partono d spigoli ciascuno. Ogni spigolo connette due vertici per cui moltiplicando il grado per i vertici conto due volte ciascuno spigolo da cui: vd=2s


Dimostrare che la distanza è proprio una distanza, ossia che d(X,X) = 0, d(X,Y)=d(Y,X) e che vale la diseguaglianza triangolare d(X,Y) + d(Y,Z) >= d(X,Z).
D(X,X)=0 perché non c’è bisogno di archi per andare da X a X; d(X,Y)=d(Y,X) perché il percorso minimo è invertibile(rimanendo sempre il minimo); d(X,Y) + d(Y,Z) >= d(X,Z) perché è possibile l’uguaglianza (passando per Y) quindi visto che la distanza è il min percorso non sarà mai d(X,Y) + d(Y,Z) < d(X,Z).


Calcolare il numero di archi di un grafo aciclico, in funzione dei vertici e delle cp.ti cn.se.
Analizzo prima le componenti connesse. Chiamo radice un vertice e posso pensare che i vertici di livello inferiore “creino” quelli di livello superiore. Inoltre posso ordinare queste creazioni temoporalmente(in senso antiorario a partire da un vertice di livello uno). Ogni creazione costruisce un arco. Le creazioni sono una meno dei vertici(la radice non è creata con archi..). per cui il numero minimo di archi è A=V-1.
Ma A>V-1 è assurdo perché se un vertice si connette a un vertice “non nuovo”(non neonato..e non il vertice genitore) si creano due strade per arrivare alla radice partendo da quel vertice; queste due strade hanno almeno un altro nodo in comune(la radice) quindi si crea un ciclo.
All’interno delle c.c. A_1=V_1-1; sommando n(con n = numero di c.c.) volte questa equazione ottengo A_1+A_2+…+A_n= V_1+…+V_n –n ovvero A=V-n


Dimostrare che in un albero i nodi di livello massimo sono foglie. E' vero il viceversa?
Supponiamo falsa la th: i nodi avrebbero un altro collegamento(riprendendo il paragone di prima oltre a quello del genitore)che può essere: a livello più alto(falso perché siamo a livello massimale) o più basso (o =) ma in questo caso si creerebbe un ciclo che è falso perché un’albero è aciclico.
Mi sembra che il viceversa sia vero perché le foglie sono definite solo all’interno di un’albero.


Dimostrare che ogni nodo ha un unico arco che lo congiunge ad un nodo di livello inferiore. Usare questo fatto per dimostrare che il percorso che congiunge ogni vertice alla radice è unico; che dati due qualunque vertici, il percorso che li congiunge è unico.
Se un nodo avesse due o più archi con i livelli inferiori si creerebbe un ciclo(due strade che si intersecano in almeno due nodi prima della o nella radici creando un ciclo). se un vertice ha un solo arco per i livelli inferiori c’è solo una strada(un solo arco quindi un solo percorso) per arrivare al livello 0 (la radice). Visto che la scelta della radice è arbitraria dati due vertici posso considerere la radice uno dei due e quindi ricadere nel caso precedente.


In un albero si sa che la radice ha grado r, le foglie sono tutte al livello h(ops ho usato n nelle formule..) e i nodi intermedi hanno tutti grado d. Calcolare il numero di foglie e il numero totale di vertici.
Cancellando la radice e gli r archi ad essa adiacenti rimango con r sottografi “uguali” tra loro in cui i nodi intermedi sono di grado d. analizzo uno di essi: avrà una radice di grado d-1(per la cancellazione effettuata) che crea d-1 vertici i quali creano a loro volta d-1 e così via fino alle foglie. Totale vertici: $ (d-1)^0+(d-1)^1+…+(d-1)^{n-1} = \frac {(d-1)^n-1}{d-2} $ . Tornando al caso originale devo moltiplicare per r e aggiungere la radice: $ r( \frac {(d-1)^n-1}{d-2})+1 $ .
analogamente trovo il totale delle foglie: $ r(d-1)^{n-1} $

Dimostrare che il grafo completo con 5 vertici e il grafo bipartito (3,3) non sono planari. Dimostrare che un qualunque grafo bipartito (n,2) è planare.
Non riesco a formalizzare bene questi due:
1)Prima disegno i contorni del grafo .Posso fare passare gli spigoli dentro o fuori i contorni del grafo. Dentro i contorni del grafo(ovvero il poligono di cinque lati anche concavo) ne posso disegnare max 2 senza intersezioni. Anche fuori posso disegnarne max 2(si vede con qualche semplice disegno) per cui posso disegnare max 4+5 archi. Ma ne servono $ { 5 \choose 2} = \frac{5(4)}{2}=10 $quindi non è planare.
2)analogamente a prima disegno i contorni della poligonale di 6 lati (anche concava o intrecciata) in rosso(AAABBB prendendo spunto dai due insiemi) e in blu coloro gli archi del grafo che dovrebbero essere 9. Noto che usando i confini della poligonale posso al massimo disegnare 5 archi blu dentro. Fuori posso massimo 3 senza intersezioni(si può vedere con disegni..ma non riesco a formalizzarlo) per cui arrivo a 8 e non 9.
Ogni grafo bipartito(n,2) è planare perché può essere disegnato così: si possono disporre gli n vertici rossi lungo una retta e i due vertici”blu” in due semipiani diversi e condurre i segmenti(che hanno un solo punto d’intersezione tra loro ovvero il vertice di partenza se giacciono in due semipiano distinti o il vertice d’arrivo.)

Dimostrare che un albero è un grafo planare.
Chiamato un vertice radice posso disporre il grafo in una “tabella” senza intersezioni con questa strategia:
la radice ha grado n; divido il piano in n parti(con n-1 rette) e in ciascuna di esse dispongo lungo la stessa retta perpendicolare alle divisioni del piano gli n vertici di livello 1. In ciascun vertice a livello uno ripeto l’operazione verso il basso dividendo nuovamente in porzioni sempre più piccole lo spazio. Arriverò a disegnare tutto l’albero senza intersezioni quindi è planare.

[Numeri di Ramsey] Se coloriamo gli archi di un grafo completo con 6 vertici in rosso o blu, allora esiste un triangolo monocromatico. Dimostrare che 6 è il minimo possibile.
Con 5 vertici posso disegnare il poligono di un colore e le diagonali di un altro senza ottenere triangoli; con quattro vertici lo stesso e con 3 vertici due lati di un colore e il terzo di un altro.

Nel caso che abbia esattamente due vertici di grado dispari, dove si trovano gli estremi del percorso?
Se entro in un vertice devo uscire per un percorso diverso quindi se entro e esco mi servono un numer pari di archi. Se entro solo(fine) o esco solo(inizio) posso avere un numero dispari.

Buona serata Simone
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

enomis_costa88 ha scritto:Quanti archi ha un grafo bipartito [completo] con m vertici blu e n vertici rossi? Quanto vale il grado di ogni suo vertice? Quanto vale il suo diametro?
[...]
Il diametro è due perché se due vertici sono di colore diverso esiste un arco che li connette; se sono dello stesso colore vado da A ad un qualsiasi B di colore diverso dal quale posso andare in tutti i vertici del colore di A.
Quasi giusto. E' vero, tranne per un caso particolare di (m,n). Quale? (N.B.: non sto considerando m o n = 0).
enomis_costa88 ha scritto:Dimostrare che in un albero i nodi di livello massimo sono foglie. E' vero il viceversa?
[...]
Mi sembra che il viceversa sia vero perché le foglie sono definite solo all’interno di un’albero.
Aspetta, non avere fretta. Ti sto chiedendo di dimostrare/confutare il claim:

In un albero, se un vertice è una foglia, allora è di livello massimo. E' più facile di qunto non possa sembrare.

Le tue dimostrazioni sugli alberi mi piacciono molto. Bella l'idea di "sradicare l'albero...".
enomis_costa88 ha scritto:Dimostrare che il grafo completo con 5 vertici e il grafo bipartito (3,3) non sono planari. Dimostrare che un qualunque grafo bipartito (n,2) è planare.

Non riesco a formalizzare bene questi due:
1)Prima disegno i contorni del grafo .Posso fare passare gli spigoli dentro o fuori i contorni del grafo. Dentro i contorni del grafo(ovvero il poligono di cinque lati anche concavo)
Qui non ci siamo. Se disegni i contorni potresti anche avere un quadrilatero (un triangolo) che racchiude 1 (2) punti isolati. Come si adatta la tua idea a questi altri due casi? Idem, sul bipartito (3,3). Nota: questo secondo grafo è alla base di un problema notissimo, quello delle tre case e tre pozzi.

Mentre Enomis riempie i casi mancanti della sua dimostrazione, qualche altra idea?
enomis_costa88 ha scritto:[Numeri di Ramsey] Se coloriamo gli archi di un grafo completo con 6 vertici in rosso o blu, allora esiste un triangolo monocromatico. Dimostrare che 6 è il minimo possibile.

Con 5 vertici posso disegnare il poligono di un colore e le diagonali di un altro senza ottenere triangoli; con quattro vertici lo stesso e con 3 vertici due lati di un colore e il terzo di un altro.
Ok. Mi bastava con 5 vertici (per meno vertici estrai un sottografo completo dal grafo 5-completo colorato). Qui dimostri che per avere un triangolo monocromatico obbligato ci vogliono almeno 6 vertici. Quel che manca è che con 6 il t.m.c.o. c'è per davvero.

Nota a margine: nel caso 5 il controesempio di Enomis è sostanzialmente obbligato.
enomis_costa88 ha scritto:Nel caso che abbia esattamente due vertici di grado dispari, dove si trovano gli estremi del percorso?

Se entro in un vertice devo uscire per un percorso diverso quindi se entro e esco mi servono un numer pari di archi. Se entro solo(fine) o esco solo(inizio) posso avere un numero dispari.
...e quindi?
enomis_costa88 ha scritto:Buona serata Simone
Buona serata a te. Nel complesso mi sembra un buon lavoro.

M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Rispondi