Úloha 6.u3: Doplnění grafu (5 b)

Zadáno v čísle 23.6.

Řešeno v čísle 23.8.

Zadání

Na začátku máme $n$ osídlených planet tvořících planetární uskupení, mezi kterými vedou přímá meziplanetární spojení. Osídlení v galaxii se však zahušťuje a s růstem populace musí držet krok i dopravní infrastruktura. Operací asimilace nazveme začlenění nějaké osídlené planety do našeho planetárního uskupení a následné vybudování libovolně mnoha přímých meziplanetárních tahů mezi touto planetou a libovolnými jinými již osídlenými planetami z našeho uskupení.

Pomocí operace asimilace získejte planetární uskupení, kde z každé planety vede přesně $n$ přímých meziplanetárních tahů. Navíc

  • Operaci asimilace můžete použít maximálně $n$-krát.

  • Operaci asimilace můžete použít kolikrát chcete, ale velikost největší planetární unie ve výsledném planetárním uskupení musí být stejná jako velikost největší planetární unie v původním planetárním uskupení. Planetární unií rozumíme skupinu osídlených planet, u kterých o každých dvou planetách platí, že mezi nimi existuje přímý meziplanetární tah.

Řešení

Nejprve trocha terminologie z teorie grafů (k vyřešení úlohy nebylo potřeba ji znát, ale bude se nám s ní o úloze lépe mluvit, zejména s lidmi, kteří nejsou experty zrovna v galaktickém plánování). Naše původní planetární uskupení je graf – obsahuje vrcholy (planety) a hrany (meziplanetární spojení). Planetární unie je potom úplný graf, resp. klika, pokud o ní mluvíme jako o součásti nějakého většího grafu. Počet hran vedoucích z vrcholu označujeme jako jeho stupeň.

Část a) vyřešíme tak, že si k původnímu grafu $G$ přidáme jeho kopii $G’$. Za každý vrchol $v$$G$ bude v $G’$ vrchol $v’$. V kopii povedou hrany stejně jako v původním grafu, tedy mezi $u’$ a $v’$ povede hrana, právě když vede hrana mezi $u$ a $v$. Dále nataháme hrany mezi $G$ a $G’$ tak, aby mezi vrcholy $u$ a $v’$ vedla hrana právě tehdy, když mezi $u$ a $v$ hrana nevede. Pak bude každý vrchol jakoby spojený se všemi z původních $n$ (včetně sebe sama), jen bude jeho soused někdy původní vrchol a někdy kopie. Každý vrchol tedy bude mít stupeň $n$, jak bylo požadováno. Příklad konstrukce je vidět na obrázku 1.

Obrázek 1: Dva příklady konstrukce grafu nepřidávající více než $n$ vrcholů. Přidané vrcholy jsou bílé, přidané hrany čárkované.

Dovedeme takový graf vyrobit pomocí asimilací? Jistě, budeme nové vrcholy přidávat po jednom v libovolném pořadí a pro každou hranu, která má z právě přidávaného vrcholu vést, se podíváme, jestli už existuje vrchol na jejím druhém konci. Pokud ano, šup tam s ní. Pokud ne, vytvoříme ji až během přidávání toho druhého vrcholu.

Nyní k části b). Výše uvedený postup nestačí, příklad grafu, při jehož rozšiřování vytvoří větší kliku, než tam původně byla, je na obrázku 1 vpravo. Budeme si muset poradit jinak. Držte si klobouky, je čas na pořádnou expanzi galaktického společenství.

Opakujeme následující: Pokud je nejmenší stupeň v grafu roven $n$, skončíme. Jinak si pořídíme kopii stávajícího grafu a přidáme hranu mezi vrchol $v$ a jeho kopii $v’$ právě tehdy, když $v$ patřil mezi vrcholy s nejmenším stupněm. Příklad konstrukce je na obrázku 2.

Obrázek 2: Příklad konstrukce grafu nevytvářející větší kliky. Celkem proběhnou tři kroky. Vrcholy přidávané v daném kroku jsou bílé, přidané hrany čárkované.

Takto se v každém kroku zvýší nejmenší stupeň v grafu o 1 (a počet vrcholů se zdvojnásobí). Nejpozději za $n-1$ kroků bude tedy každý vrchol stupně $n$ a skončíme.

Tímto způsobem nevytvoříme žádnou kliku větší, než byla největší klika v původním grafu (kromě případu, kdy v původním grafu byl alespoň jeden vrchol, ale nebyla v něm žádná hrana – tehdy ovšem nemá část b) řešení). V kopii $G’$ stávajícího grafu $G$ jistě není větší klika a hrany vedoucí mezi $G$ a $G’$ nepřidají žádnou kliku na více než dvou vrcholech – nejsou součástí ani trojúhelníku, natož nějaké větší kliky, protože mezi $G$ a $G’$ vede z každého vrcholu nejvýše jedna hrana.

Matěj