a) Az I. fejezet 16. feladatában beláttuk, hogy ha egy 3n tagú társaságban bármely két embernek van közös ismerőse, akkor van közöttük n ember, aki együtt az összes többit ismeri, sot van n+1 ember, aki együtt mindenkit ismer. Mi a helyzet akkor, ha a feltételt némileg gyengítjük és csak annyit feltételezünk, hogy a társaság ismeretség-gráfja 2-átmérőjű, azaz csak annyit feltételezünk, hogy bármely két egymást nem ismerő embernek van közös ismerőse?
b) Az I. fejezet 26. feladatában élesítettük a 16. feladat állítását és bebizonyítottuk, hogy n embernél lényegesen kevesebb is van, akik együtt a társaság minden tagját ismerik. Mi a helyzet, ha a társaság ismeretség-gráfjáról csak annyit követelünk meg, hogy 2-átmérőjű?
| TARTALOMJEGYZÉK |