Rozsupływanie grafów

Zawsze lubiłem teorię grafów. Niestety, ta sympatia jest w dużym stopniu nieodwzajemniona, gdyż z obejmującej tę teorię matematyki dyskretnej nie miałem zbyt dobrych ocen :) Mimo to chciałbym dzisiaj polecić pewną grę ściśle związaną z tą dziedziną.

Chodzi o Planarity. Polega ona na tym, by ułożyć wierzchołki danego grafu planarnego tak, by żadne jego krawędzie się nie przecinały. Dla małych grafów jest to oczywiście proste, lecz gdy liczba wierzchołków przekracza kilkanaście, na rysunku zaczyna być już gęsto…

Na forum Warsztatu pojawił się wątek z pytaniem o jakiś systematyczny sposób na odpowiednie ułożenie wierzchołków w tej grze. Z faktu, że o tej pory nie znaleziono tam żadnego pewnego rozwiązania wynika, że to całkiem interesująca gra ;)

Be Sociable, Share!

• 
• 

Be Sociable, Share!

• 
• 

• Tweet
•