[C] Grafi grandiosi

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

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

Messaggioda Marco » 01 gen 1970, 01:33

Pescato da Kalva. <BR> <BR>[olimpiade brasiliana 2003] <BR>------------------ <BR>Un grafo G con n vertici è detto <!-- BBCode Start --><I>grandioso</I><!-- BBCode End --> se possiamo etichettare ogni vertice con un diverso intero positivo non maggiore di [n<sup>2</sup> / 4] e trovare un insieme D di interi non negativi, tale per cui in G c\'è un arco tra due vertici se e solo se la differenza tra le loro etichette è in D. <BR> <BR>Dimostrare che se n è sufficientemente grande, possiamo sempre trovare un grafo con n vertici che non sia grandioso. <BR>------------------ <BR>Come al solito, [x] è la parte intera di x. <BR> <BR>Ciao. M.[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Torna a “[vecchio forum]Proponi gli esercizi”

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti