Zdravo,
ali mi morda lahko kdo svetuje, kje se da dobiti kaksno spletno aplikacijo, ki bi prikazovala Ramseyeva stevila (zanimata me samo dve barvi, npr. rdeca in modra)?
Hvala!
Ramseyeva stevila
Re: Ramseyeva stevila
Ni mi npr. jasno, zakaj je iz definicije jasno, da je R(2,m) = m
Re: Ramseyeva stevila
Glede \(R(2,m)\):
to je velikost najmanjšega polnega grafa, v katerem ne glede na izbiro barvanja povezav z dvema barvama (modro in rdečo), najdemo moder poln podgraf velikosti 2 (torej modro povezavo) ali pa rdeč poln podgraf velikosti \(m\).
Najprej pokažemo \(R(2,m)\ge m\): če namreč vse povezave polnega grafa velikosti \(k\), \(k<m\), pobarvamo z rdečo, v njem ne najdemo nobenega od zgoraj opisanih podgrafov.
Če pa poln graf na \(m\) točkah pobarvamo na poljuben način, bodisi vsebuje modro povezavo bodisi so vse povezave rdeče. Zato ustreza zgornjemu pogoju in velja \(R(2,m)\le m\).
to je velikost najmanjšega polnega grafa, v katerem ne glede na izbiro barvanja povezav z dvema barvama (modro in rdečo), najdemo moder poln podgraf velikosti 2 (torej modro povezavo) ali pa rdeč poln podgraf velikosti \(m\).
Najprej pokažemo \(R(2,m)\ge m\): če namreč vse povezave polnega grafa velikosti \(k\), \(k<m\), pobarvamo z rdečo, v njem ne najdemo nobenega od zgoraj opisanih podgrafov.
Če pa poln graf na \(m\) točkah pobarvamo na poljuben način, bodisi vsebuje modro povezavo bodisi so vse povezave rdeče. Zato ustreza zgornjemu pogoju in velja \(R(2,m)\le m\).