Pagina 1 di 1

Inviato: 01 gen 1970, 01:33
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]