Grafy Losowe Zadania

Off-topic

I. Czy poniższe (nieskończone) grafy są planarne? (taka bardziej zagadka)
cqplanar.png

II. Pierwszy rysunek przedstawia nawinięcie pewnego grafu na torus. Czy te grafy są izomorficzne? (to raczej ciekawostka z wikipedii :D)
240px-Shrikhande_torus.svg.png
250px-Shrikhande_graph_symmetrical.svg.png

III. Niech V będzie zbiorym tych liczb naturalnych v, dla których istnieje dokładnie v/3 liczb względnie pierwszych z v mniejszych od v. Niech G będzie grafem o wierzchołkach V, w którym krawędzie łączą te i tylko te wierzchołki u,v (u różne od v), że u+v należy do V. Niech H będzie grafem o wierzchołkach będącymi punktami kratowymi na płaszczyźnie (o współrzędnych całkowitych dodatnich), połączonych krawędzią wtedy i tylko wtedy gdy sąsiadują ze sobą (są oddalone o jedną kratkę pionowo lub poziomo) lub są oddalone o trzy kratki poziomo.
Udowodnij, że grafy G i H są izomorficzne.
(to raczej teoria liczb, dość trudna i naciągana, a izomorfizm ma tu akurat małe znaczenie)

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License