[C] Grafi grandiosi

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

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

Messaggio da Marco »

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."
Bloccato