Segítene valaki ebben a feladatban?

Question

Egy kilencfős csapatról tudjuk, hogy mindenki pontosan négy másik embert ismer a csapat tagjai közül. (Az ismeretség kölcsönös.)

a,Lehetséges-e, hogy a csapat tagjai között bármely két embernek van közös ismerőse?

b)Igaz-e, hogy egy ilyen csapat tagjai között bármely két ember vagy ismeri egymást, vagy van közös ismerősük?

Answer 1

a) Lehetséges. Az ilyen jellegű kapcsolati hálót hálózati gráfként ábrázolva, ha egy kilencfős csapat tagjai között mindenki pontosan négy másik embert ismer, akkor ez egy komplett gráfot jelent, amelynek 9 csúcsa és 36 éle van. Egy ilyen gráfban minden pár csúcs között van legalább egy közös szomszéd, tehát van közös ismerősük.

b) Igaz. Ha a csapat tagjai között mindenki pontosan négy másik embert ismer, akkor minden pár csúcs között van legalább egy közös szomszéd, tehát ha két embernek van közös szomszéduk, akkor ismerik is egymást. Ha nincs közös szomszéd, akkor ismerik egymást.

Comments

Köszönöm a segítséget!