Ramseyjev izrek

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Ramseyjeva števila

Definicija: R(m,n) (Ramseyjeva števila) - najmanjše število N, tako da ima vsak neusmerjen graf na N ali več točkah poln podgraf (klika) moči m ali pa prazen podgraf (antiklika) moči n.

Lastnosti:

  • R(m,n) = R(n,m) (pogledamo komplement grafa)
  • težko izračunljiva za poljubna m in n
  • R(1, n) = 1
  • R(2, n) = n

Ramseyjev izrek

Ramseyjeva števila vedno obstajajo in velja: R(m, n) \leq R(m-1, n) + R(m, n-1) \ \mbox{za} \ m,n \geq 2


Posledice:

  • R(m,n) \leq {{m+n-2} \choose {m-1}}
  • R(m,n) \geq 2^{n \over 2} \ \mbox{za} \ n \geq 1


Povezave

Vzpostavljeno iz »http://www.e-studij.si/Ramseyjev_izrek«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja