Grafi

[enomis_costa88]

Qualche risposta(numerate secondo le osservazioni di marco..):
1) se n=m=1 il diametro è uno perché la distanza tra gli unici due vertici è uno.
2) avevo completamente frainteso il viceversa (pensavo si intendesse: se i nodi a livello massimale sono foglie siamo in un albero..). Il viceversa è falso perché posso disegnare un albero la cui radici sia di grado due e i vertici del primo livello di grado uno e due..avrei una foglia non a livello massimale(ci sarebbe almeno un secondo livello).
5) quindi gli estremi devono essere nei due vertici dispari(nei vertici non estremi entro e esco e mi servono come già spiegato un numero pari di archi).
3) ci stò lavorando..
4) mi manca la dimostrazione che con 6 esiste sempre il triangolo monocromatico.
Soluzione brute force (so che dovrei vergognarmi anche solo a pensarla..ma oggi il mio cervello era in sciopero): è comodo lavorare con un’esagono regolare e visto che ci interessa solo la combinatoria del grafo e non la forma supponiamolo così (al massimo si può spostare qualche vertice e deformare il tutto.)
Distinguo 8 casi: tutto il perimetro è di un colore, solo un lato è rosso, due lati consecutivi sono rossi, due lati che distano solo un lato sono rossi, due lati opposti sono rossi, tre lati consecutivi sono rossi, due lati consecutivi e uno no rossi e tre lati nessuno dei quali consecutivi lo è.
Se il perimetro è tutto di un colore le diagonali possono formare ancora due triangoli dell’altro colore che non possono essere “bloccati” senza formare un triangolo con i lati perimetrali.
Se un lato è rosso e 5 blu: per comodità do dei nomi ai vertici(A,…,F con AB rosso). Devo bloccare i triangoli AEC e BDF e posso solo con AC e BF blu. Ora devo bloccare ABD ma non posso.
Se due lati consecutivi sono rossi e il restanti 4 blu: AB,BC rossi. Devo bloccare ABC quindi AC è blu. Per BCF ci vuole BF ma non posso più bloccare BCE.
Se AB,FE sono rossi e i restanti blu: devo bloccare FEC con FC,ABD con AD. Ora non posso bloccare BDF.
Se AB,DE sono rossi: devo bloccare ABD, ABE con AD,BE;non posso più bloccare BDF.
Se AB,BC,CD sono rossi: per ABC e BCD devo usare AC,BD blu. Non posso con ABE.
Se AB,BC, De sono rossi: AC deve essere blu. Non posso bloccare ADE.
Se AB,CD,FE sono rossi: devo bloccare il triangolo BDF e ho tre possibilità(BF,BD,DF) ma la figura è piuttosto simmetrica ed è ininfluente cosa scelgo.. scelgo BF blu. Ora so che FC deve essere rosso per impedire il triangolo BFC. Per impedire FCD e FCE devo colorare di blu FD e CE. Ora non posso più bloccare ABD.
Proprio ora mi stà venendo in mente ciò che potrebbe essere un incipit per un’altra dimos: se coloro 3 lati che non hanno vertici in comune di rosso impedisco 12 triangoli blu (quattro ciascuno perché $ \frac {3*{ 6\choose 3}}{{6 \choose 2}}=4 $); poi posso colorare altri tre lati che hanno però due vertici in comune con gli altri già rossi che impediscono 2 triangoli ciascuno. Dopo questi tre non posso più impedire nulla. I triangoli impediti sono 18 ma $ {6 \choose 3}=20 $ per cui ne rimarrebbero ancora 2..ma non mi pare per niente rigoroso(almeno come l'ho scritto io ora).

Buona Nottata (per cambiare ) Simone

[enomis_costa88]

Dimostrare che il grafo completo con 5 vertici non è planare.
1) Se disegnando i confini risulta un pentagono: dopo avere disegnato internamente due archi non intersecatisi noto che questi due devono avere almeno un estremo in comune perché:
dopo avere disegnato un arco non posso più disegnare archi passanti per un vertice(il vertice che ha un lato in comune con tutti e due gli estremi dell’arco disegnato), se voglio evitare gli altri due vertici già interessati dall’arco disegnato mi rimane solo una coppia di vertici possibili che però è già collegata da un lato. Quindi i due archi devono avere un vertice in comune. Inoltre non si possono disegnare diagonali(o archi) verso i due punti non ancora interessati senza intersecare i due già disegnati. Dentro posso disegnarne massimo due. Ora un vertice è già collegato a tutti gli altri e quindi è inutile usarlo. Analogamente a prima posso dimostrare che anche fuori due archi devono avere un vertice in comune sostituendo però al vertice prima tagliato fuori dal primo arco disegnato quello che ora è già collegato con tutti. Inoltre rimango con due punti chiusi dagli ultimi due archi disegnati verso i quali non possono più giungere ne partire archi. Anche fuori il massimo è due.
2) Caso in cui disegnando i contorni rimango con un triangolo e dentro due punti isolati:
chiamo ABE il triangolo e C,D i due punti isolati (immaginate tutto in un piano cartesiano..C è quello con l’ascissa più vicina a B e D è l’ultimo punto che rimane..) allora posso disegnare il pentagono concavo ABCDE che è un poligono quindi i suoi lati non hanno alcun tipo di intersezioni tra loro.
Posso applicare paro paro il ragionamento di prima visto che in nessun punto di esso avevo supposto il pentagono convesso (anzi avevo parlato di archi..e non di diagonali) e gli archi che potrebbero esistere in esso sono gli stessi 5 dentro e 5 fuori..massimo due senza intersezioni dentro e massimo2 fuori.
3) Caso in cui disegnando i contorni mi risulta un quadrilatero con dentro un punto isolato.
Chiamo A il punto isolato e BCDE il quadrilatero. Posso disegnare il pentagono concavo ABCDE e ricadere nei casi precedenti.. e questo conclude la dimos..i hope.

se tutto va bene ora concludo il bipartito 3,3 che è un problema con il quale ho una lunga storia in corso..mi era stato proposto tanto tanto tempo fa(quando facevo le elementari..)da un ragazzo un po' più vecchio di me (faceva le medie) che non riusciva a risolverlo (ne a me ne a lui nessuno aveva detto che è impossibile)..questo problema allora mi aveva fatto dormire veramente poco.

[enomis_costa88]

forse dopo anni..
Il grafo bipartito completo (3,3) non è planare:
nota: non supporrò in nessun ragionamento la convessità del poligono. Inoltre se sei vertici formano un poligono esiste una regione interna e una esterna. In un poligono concavo gli archi possono internamente al poligono creare tutti i collegamenti che creerebbero le diagonali in uno convesso(e rimangono invariate anche le incidenze). Quindi possiamo pensare a una deformazione del poligono regolare esagono che lo renda non regolare o addirittura concavo mantenendo le incidenze tra archi che non rimangono più diagonali. In ogni caso visto che non ho dimostrato l’esistenza di questa trasformazione ma l’ho solo supposta mi limito a notare che per la prima frase detta ciò che segue vale anche nei concavi(tant'è vero che io ho lavorato con esagoni concavi..).

Step 1 dimostro che posso sempre disegnare un esagono in ogni caso.
Divido in quattro sottocasi: a seconda della figura che mi risulta dopo avere disegnato i contorni. Se mi risulta un esagono sono a posto. Se mi risulta un triangolo con 3 punti isolati interni procedo così: nomino ABF il triangolo e sempre pensando i restanti punti nel piano cartesiano chiamo C il punto col l’ascissa più vicina a B,E quello con l’ascissa più vicina a F e D il rimanente. Ora posso disegnare il poligono (esagono concavo) ABCDEF. Se mi risulta un quadrilatero con dentro due punti isolati chiamo ABCF il quadrilatero, D il punto con l’ascissa più vicina a C e E il rimanente ora posso disegnare l’esagono. Nell’ultimo caso ovvero un pentagono che racchiude un punto isolato agisco analogamente: ABCDE il pentagono e F il punto isolato e poi disegno l’esagono.

Step2 Ora analizzo come possono disporsi lungo il poligono i due gruppi(A,Bsono i due gruppi). I modi possibili sono tre (da immaginarsi disposti su di un tavolo senza sapere dove inizia e dove finisce la stringa): ABABAB; AAABBB;AABABB ovvero con nessuna A consecutiva, con tre A consecutive e con due A consecutive(idem per B).

Step3 analizzo il primo caso ABABAB. Noto che vi sono 6 collegamenti lungo i confini del poligono( stiamo parlando di archi quindi anche un po’ dentro o un po’ fuori..il che non cambia il problema..anzi quando parlerò di confine del poligono d’ora in poi, ovvero anche nei casi successivi se vi sono archi sui confini, immaginatevi gli archi e non i lati dello stesso).
Dentro il poligono ce ne può stare massimo uno. Infatti questo arco dividerebbe in due parti l’esagono con un’AB nella prima regione e AB nella seconda. I collegamenti devono quindi andare da una regione all’altra ma non possono. Analogamente si dimostra che neppure fuori si possono effettuare più di un collegamento(anche questo dividerebbe lo spazio esterno in due regioni una chiusa con AB interno e una aperta con AB). Il numero massimo di collegamenti fattibili diventa quindi 8 ma ne servirebbero9..

Step4 AAABBB. Do dei nomi ai vertici ovvero ABCDEF ai vertici ABBBAA(non chiedetemi il motivo di questa disposizione so che sarebbe stato più comodo con AAABBB). Sui confini ho 2 archi. Ora analizzo gli archi interni che partono dal gruppo B verso A (sono gli stessi che vanno da A a B visto che è bipartito..). Almeno un arco deve partire da C (perché B e D hanno 4 archi possibili ma DA interseca entrambi gli archi di B e BE entrambi quelli di D). Da B si può andare a F o a E(ovviamente in funzione degli archi di C..); se è disegnato CA non posso usare B e quindi le possibili terne sono: (CA,CF,CE)(CA,CF,DF)(CA,DA,DF); se è disegnato CF(e non CA..) posso usare BF(ma poi solo CEoDF); se è disegnato CE posso BF;BE (con CA,CF non disegnati).e nient’altro..in ogni caso solo 3 segmenti. Inoltre lo stesso ragionamento è applicabile per dimostrare che anche fuori ci stanno max 3 archi..
Quindi max fuori(3)+max dentro(3) +confine(2) =8 e non9..

Step5 AABABB. Sul confine ho 4 archi da disegnare. Do dei nomi: ABCDEF ai vertici AABABB. Internamente: Se l’arco AC è disegnato B è fuori uso e D si può collegare ad ad F e solo se AE non c’è..quindi ho massimo due archi in questo sottocaso. Se AC non è disegnato: gli archi possibili sono AE/BF/BE/DF..AE interseca con BF,DF e può stare solo con BE. Se anche AE non c’è ho tre archi (BF/BE/DF) ma DF,BE incidono e non possono coesistere..quini ne ho massimo 2 dentro.
Inoltre come prima lo stesso ragionamento è applicabile fuori quindi 2 è il massimo anche fuori.. 2+2+4 = 8 ma me ne servono 9..quindi non è planare..almeno spero ..

[Marco]

Allora, il completo 5 mi sembra a posto. Con "le case e i pozzi" confesso che mi sono perso a metà del ragionamento. Ci riprovo quando ho il tempo da metterci con la testa. Comunque, se mi si permette una critica costruttiva, entrambe le soluzioni, per quanto corrette, tradiscono la loro "ingenuità" (nel senso di naif).

La dimostrazione classica è breve e spiazzante. Si tratta di trovare lo strumento giusto per scardinare il problema. Hint in piccolo per chi vuol saperne di più (per vederlo, citare il messaggio o copiaeincolla su un editor di testo):

HINT:F + V = S + 2. Quando si parla di grafi planari, val sempre la pena di tentare con la formula di Euler. Magari non basta da sola per finire, ma dà sempre un valido aiuto.

Alla prox.

M.

[Sisifo]

Eccomi qua! Scusate il ritardo, ma non ho avuto molto tempo... Complimenti a Marco per la spiegazione come al solito chiarissima.

15) Caso 2 colori. Per 5 nodi credo sia già stato dato il controesempio. Per 6 nodi. Considero un nodo arbitrario N. Poichè da N partono 5 archi, ne esistono almeno 3 dello stesso colore (diciamo del colore C). Questi tre archi mandano in tre nodi $ M_1 \quad M_2 \quad M_3 $. Ora se tra due di questi nodi esiste un arco del colore C, allora la terna composta da questi due nodi e dal nodo N soddisfa le condizioni richieste. Altrimenti le soddisfa la terna $ M_1 \quad M_2 \quad M_3 $.
Caso 3 colori. Come prima scegliamo un nodo N. Come prima esistono almeno 6 archi dello stesso colore. Se tra questi sei nodi ce ne sono due collegati da un arco dello stesso colore di prima OK, altrimenti abbiamo sei nodi collegati completamente fra loro da archi appartenenti a due colori e per il caso due colori concludiamo.

[Marco]

Ok, Sisifo: questa è la dimostrazione classica. Una costruzione del caso con 3 colori e 16 vertici?