dotNETportal.cz

Rozhodl jsem se, že také občas něco napíšu sem do blogu. Když mě napadne nějaká zajímavá aplikace, udělám pěknou fotku, video, nebo jenom tak, když něco objevím.

Jsem v prváku na matfyzu (Univerzita Karlova v Praze), na informatice. V rámci diskrétní matematiky (teorie grafů) mě zaujala jedna pěkná úloha. Rovinný graf je takový, kde se mezi jeho vrcholy nekříží žádné hrany. Stupněm vrcholu nějakého grafu se rozumí počet hran jdoucích do tohoto vrcholu. A teď si představme takový rovinný graf, že všechny jeho vrcholy jsou stejného stupně, například 2, 3... Když se opravdu nakreslí tak, aby se nekřížily žádné hrany, vzniknou docela pěkné, pravidelné "obrázky".

Naprogramoval jsem si jednoduchou aplikaci v jazyku C# a s pomocí tabletu jsem si chvilku hrál se šoupáním bodů. První tlačítko nebo dvojklik "tužkou" bylo umístění nového bodu, druhé tlačítko (obdoba pravého na myši) bylo umístění nové hrany. Táhnutím byl posun bodu. Vykresloval jsem pomocí GDI+ (metod DrawLine(), FillEllipse() atd.), zdrojáky sem ale nedávám. Bylo to psané hodně narychlo a určitě něco podobného každý zvládne sám.

Pro stupeň vrcholů 2 je to jednoduché - stačí propojit tři body a s méně to už určitě nepůjde:

Pro stupeň 3 ho můžeme na všechny strany rozšířit o jeden bod a vznikne nám takovýhle graf:

Určitě by to šlo ale udělat na méně bodů, tenhle graf je už složen jenom z trojúhelníků. To už také nepůjde moc vylepšit:

Pro stupeň 4 vznikne zase moc pěkný obrázek, ale protože uprostřed je čtverec, takže by šlo určitě pár bodů ubrat:

U stupně 5 to začne být zajímavé. Když vyjdeme z pětiúhelníku, vznikne symetrický graf na dvaceti vrcholech:

Ten jde ale zjednodušit jen na 12 vrcholů:

Zvládnete sestavit podobný rovinný graf, kde každý vrchol bude mít stupeň 6? Nebo více? Najít obecný algoritmus, jak takový graf sestavit? Zkuste si ho nakreslit...