Téma t3: Mafie jako výpočetní model

Zadáno v čísle 24.1.

Zadání

Za sedmero horami a sedmero řekami v jednom odlehlém městečku byla mafie. Jak taková mafie vypadá? Skládá se z mafiánů. Žádný mafián samozřejmě z bezpečnostních důvodů nezná všechny ostatní mafiány – každý jich zná jen konstantně mnoho a s těmi si dopisuje. Každý den ráno pošle všem svým známým mafiánům dopis. (Každá dvojice známých mafiánů si tedy každý den pošle dva dopisy – v každém směru jeden.) Všechny dopisy se do večera doručí. Mohli bychom tedy říci, že celá mafie má strukturu souvislého grafu1. Vrcholy odpovídají mafiánům a hrany reprezentují to, zda si daná dvojice dopisuje.

Mafiáni by nyní chtěli zjistit něco o tom, jak ta jejich mafie vypadá – třeba kolik jich je. Jediný způsob, jak něco takového zjistit, je pomocí mafiánů, co se znají a posílají si dopisy. Nejdříve mafiánský boss na předem domluveném místě vylepí algoritmus, který bude popisovat, jak si mají mafiáni posílat dopisy, aby hledanou informaci zjistili. Každý den si pak známí mafiáni mohou vyměnit zprávu. Cílem je, aby na konci každý mafián věděl informaci, na kterou se snažili přijít.

Vymyslete grafové vlastnosti nebo problémy, které by mafiáni mohli řešit, nebo zkuste vyřešit jeden z problémů zmíněných v další části. Určete složitost vašeho algoritmu. Jde nám především o počet dnů, za který v nejhorším případě algoritmus skončí, a součet délek všech zpráv, které si mafiáni vymění. Jak se na každého správného mafiána sluší, má neomezený výpočetní výkon, takže časovou složitost v běžném slova smyslu uvažovat nemusíte. Složitosti můžete vyjadřovat v závislosti na počtu mafiánů, průměru grafu mafie (největší vzdálenost mezi dvojicí mafiánů), nebo si můžete vymyslet svůj vlastní parametr. Složitosti určujte asymptoticky2.

Inspirovat se můžete následujícími problémy:

  • Zjistěte velikost mafie, tedy počet mafiánů, kteří v ní jsou.

  • Mafiáni by chtěli co nejvíce omezit počet dopisů, které pošlou. Rozhodli se proto, že si spolu někteří mafiáni přestanou dopisovat. Najděte co nejvíce dvojic, které si spolu mohou přestat dopisovat tak, aby stále mezi libovolnou dvojicí mafiánů existovala cesta.

  • Mafiáni by chtěli zjistit, jaký je celkový majetek mafie (vyjádřeno v místní měně). Žádný z mafiánů při tom nechce, aby některý jiný mafián zjistil hodnotu jeho majetku.

  • Čas od času potřebuje nějaký mafián o něčem informovat všechny ostatní. To se dělá tak, že předá zprávu všem, se kterými si dopisuje. Každý další mafián pak zprávu přepošle ostatním mafiánům, se kterými si dopisuje (ale jen při prvním přijetí dané zprávy). Zjistěte, jak nejdéle může trvat, než se zpráva dostane ke všem mafiánům.

  • Mafiáni by chtěli vědět, kolik nejméně z nich by muselo být zatknuto, aby se mafie „rozpadla“. Tedy aby pak existovali dva mafiáni, mezi kterými nebude existovat cesta vedoucí pouze přes nezatčené mafiány. Jinými slovy chceme spočítat největší k takové, že graf mafie je k-souvislý. Toto by mohlo být zajímavé už pro k=2. (Věřím, že tento problém je poměrně těžký a možná ani nemá efektivní řešení.)

Kuba


1) Pokud nevíte, co se myslí grafem, doporučujeme přečíst si prvních pár odstavců grafové kuchařky zde: https://ksp.mff.cuni.cz/kucharky/grafy

2) Pokud nevíte, co se tím myslí, doporučujeme přečíst odstavec asymptotická složitost v programátorské kuchařce o složitosti: https://ksp.mff.cuni.cz/kucharky/slozitost/