Hraní si s pravidelnými grafy

Tomáš Slavíček       12. 12. 2008       Grafika       6927 zobrazení

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:

graf2_thumb

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

graf3_1_thumb[1]

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:

graf3_2_thumb[1]

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:

graf4_1_thumb[1] graf4_2_thumb[1]

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

graf5_1_thumb[1]

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

graf5_2_thumb[1]

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...

 

hodnocení článku

1 bodů / 1 hlasů       Hodnotit mohou jen registrované uživatelé.

 

Nový příspěvek

 

Diskuse: Hraní si s pravidelnými grafy

Ahoj,

už možná víš, že rovinný graf má vždy alespoň 1 vrchol stupně 5 či méně - a tudíž nelze udělat rovinný graf, který by měl všechny vrcholy stupně 6.

Jana

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Díky za odpověď, to je dobrá připomínka :) To jsem si v době psaní článku ještě neuvědomil, ale už ten závěr asi měnit nebudu. Diskrétní matematika je pěkná, stále se tam dají objevovat nové zajímavé věci.

nahlásit spamnahlásit spam 0 odpovědětodpovědět
                       
Nadpis:
Antispam: Komu se občas házejí perly?
Příspěvek bude publikován pod identitou   anonym.

Nyní zakládáte pod článkem nové diskusní vlákno.
Pokud chcete reagovat na jiný příspěvek, klikněte na tlačítko "Odpovědět" u některého diskusního příspěvku.

Nyní odpovídáte na příspěvek pod článkem. Nebo chcete raději založit nové vlákno?

 

  • Administrátoři si vyhrazují právo komentáře upravovat či mazat bez udání důvodu.
    Mazány budou zejména komentáře obsahující vulgarity nebo porušující pravidla publikování.
  • Pokud nejste zaregistrováni, Vaše IP adresa bude zveřejněna. Pokud s tímto nesouhlasíte, příspěvek neodesílejte.

přihlásit pomocí externího účtu

přihlásit pomocí jména a hesla

Uživatel:  
Heslo:  

zapomenuté heslo

 

založit nový uživatelský účet

zaregistrujte se

 
zavřít

Nahlásit spam

Opravdu chcete tento příspěvek nahlásit pro porušování pravidel fóra?

Nahlásit Zrušit

Chyba

zavřít

feedback