Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


4. Procvičování / Úloha s kamarády

Úloha z matematické olympiády [3]

Ve skupině šesti lidí existuje právě 11 dvojic známých. Vztah "znát se" je vzájemný, tzn. jestliže osoba A zná osobu B, pak B zná A. Pokud se kdokoliv ze skupiny dozví nějakou zprávu, řekne ji všem svým známým. Dokažte, že se tímto způsobem zprávu dozví nakonec všichni.

Nápověda

Kamarády si zakreslete jako vrcholy, vztah "znát se" použijte pro hrany a využijte vlastnosti úplných grafů.

Řešení

Kamarády (známé) si zakreslíme jako graf o šesti vrcholech. Graf bude neorientovaný.

Představme si situaci, že se zná každý s každým - půjde o úplný graf o 15 vrcholech (stačí dosadit do vzorce pro výpočet počtu hran v úplném grafu).

Úplný graf o 6 vrcholech - K6
K6 - úplný graf na šesti vrcholech

Ze zadání víme, že hran v grafu bude 11, tzn. z grafu 4 hrany odebereme. Každý vrchol je ale spojen s ostatními 5 vrcholy, takže i pokud odebereme 4 hrany jednomu vrcholu, graf stále zůstane souvislý (→ každá zpráva se dostane ke všem kamrádům).


Úvod

Základní pojmy

Vybrané problémy

Procvičování