Warsztat » Forum

[Gry] Teoria grafow czyli jak go rozsuplac

Feb 17, 2010 | thyros |
24 wypowiedzi na 2 stronach:
1 2
thyros
Feb 17, 2010

Teoria grafow czyli jak go rozsuplac

Witam,
Natknelem sie w sieci na dosc fajna gre logiczna: http://www.planarity.net
Przeszedlem pare poziomow i zastanawiam sie, co musi spelniac taki graf aby mozna go bylo 'rozsuplac'?
Ma ktos jakas teorie?

Pozdrawiam thyros
GorskY.exe
Feb 17, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Musi być planarny.
Xion
Feb 18, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Graf jest planarny wtedy, gdy można go narysować na płaszczyznie. A jest tak wtedy, gdy nie zawiera w sobie* grafu pełnego o 5 wierzchołkach lub grafu dwudzielnego 2x3 wierzchołki.


* tak naprawdę to warunek jest nieco silniejszy niż samo zawieranie, ale w uproszczeniu można tak powiedzieć
GorskY.exe
Feb 19, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Cytat:

Graf jest planarny wtedy, gdy można go narysować na płaszczyznie...


...tak, że jego krawędzie się nie przecinają :P
RageX
Feb 20, 2010

Odp: Teoria grafow czyli jak go rozsuplac

wszystko fajnie... ale wy podaliście warunek rozwiązania grafu, a nie jak rozwiązać taki graf.

Edit: jak narazie bez szukania po internecie sposobu... przychodzi mi na myśl tylko jedno... szukasz trójkątów... potem kwadratów... potem pięciokątów itd.

Edit@ down: Rzeczywiście w poście autor o to pyta... ale w tytule tematu jest co innego. :)
GorskY.exe
Feb 20, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Autor wątku pytał, jaki graf musi być, aby go "rozwiązać", a nie jak tego dokonać.
thyros
Feb 20, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Cytat:
Autor wątku pytał, jaki graf musi być, aby go "rozwiązać"


Tak jest. Skoro juz wiem co musi byc spelnione pomysle nad rozwiazaniem...

Dzieki za odp.
Thyros
thyros
Feb 26, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Widze, ze informacja o tym, co musi spelniac graf aby dalo sie go 'rozwiazac' nie ulatwia znalezienia rozwiazania.

Cytat:
przychodzi mi na myśl tylko jedno... szukasz trójkątów... potem kwadratów... potem pięciokątów itd.

Moglbys podpowiedziec wiecej szczegolow?

Jak na razie staralem sie robic to odwrotnie. Najpierw szukalem 'sciany' niebedacej trojkatem a pozniej do niej doklejalem kolejne.
Problem z trojkatnymi scianami jest taki, ze nie bardzo wiem jak zdecydowac, w ktora strone ma byc zwrocona.
Dla przykladu (choc pewnie i tak nie jest zbyt jasny):
|\ 
|_\
czy moze
|-/
|/

Cytat:
...lub grafu dwudzielnego 2x3 wierzchołki.

Mysle, ze chodzi raczej o graf dwudzielny K3,3 (przynajmniej tak wiki podpowiada)
nilphilus
Feb 24, 2010

Odp: Teoria grafow czyli jak go rozsuplac

thyros: wszystko jedno w którą stronę będzie zwrócone ;->

sam szukałem też ścian, ale i tak 6lvlu mi się nie chciało przechodzić ;d
thyros
Feb 25, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Cytat:
wszystko jedno w którą stronę będzie zwrócone

nie jest to do konca poprawne bo jesli zle odwroce trojkat to nastepne wiezcholki beda zalezne od poprzednich, tj. w kolejnosci dokladania.

Jestem troszke bardziej wytrwaly bo juz 12 poziom mam  ;)
Xion
Feb 24, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Cytat:
Cytat:

...lub grafu dwudzielnego 2x3 wierzchołki.

Mysle, ze chodzi raczej o graf dwudzielny K3,3 (przynajmniej tak wiki podpowiada)

Tak, graf dwudzielny pełny o 2 zbiorach po 3 wierzchołki, czyli w skrócie K3,3. Aby graf był planarny, nie może zawierać podpodziału ani K5 (pełny  o 5 wierzchołkach), ani K3,3. Podpodział polega na tym, że ścieżki o dowolnej długości możemy zredukować do pojedynczej krawędzi; po takiej redukcji powstały graf nadal nie może zawierać K5/K3,3 by był planarny.

Co do zadania "rozplanarniania" grafu, to IMHO metoda trójkątów zdaje egzamin. Jednak prawdę mówiąc grając w tę grę miałem wrażenie, że tak naprawdę nie ma tu żadnej strategii :) Po prostu zawsze po odpowiednio długim kombinowaniu to jakoś intuicyjnie wychodziło, ale tak naprawdę nie potrafię podać żadnej ścisłej zasady dla tego kombinowania.
RageX
Feb 25, 2010

Odp: Teoria grafow czyli jak go rozsuplac

haha... ja ja po tym topicu do 12 doszedłem... aż się nagle skumałem ze to w nie skończoność (teoretycznie, aż przeglądarka nie padnie)

Co ciekawe każdy kolejny szedł mi coraz szybciej i na 8 potrzebowałem 23 minut, tak na 11 już 9 min.
Najbardziej wkurza brak mozliwości zaznaczania kilku na raz, obrotu już skonstruowanego układu... punkt po punkcie trzeba przesuwać, obracać...
Zaraz odpale jeszcze raz... i spróbuje zbudować pseudo procedure na szybko... :)
Tu screen, przed chwilą strzeliłem 12(czas słaby... po przerwie dnia) :)

[URL=http://img513.imageshack.us/my.php?image=planarityth7.jpg][IMG]http://img513.imageshack.us/img513/5030/planarityth7.th.jpg[/img][/URL]

I robię tak jak napisałem:
1. Szukam trójkąta...najlepiej gdy jednen z jego wierzchołków nie ma innych połączeń niźli tylko z tym trójkątem.
2. W ten sposób mam początek układu...sprawdzam wyjścia z układu(połączenia z wierzchołkami tego trójkąta). 
3. Wybieram ten który ma najmniej "wyjść", z niego sprawdzam też ile z niego wychodzi wierzchołków(czsami wolę wrócic i sprawdzić, czy z tamtym nie będzie łatwiej.
4. próbuje zamknąć figurę... czym figura ma więcej wierzchołków, tym rzadziej jest spotykana, tym trudniej ją wyznaczyć.

Co do przestawiania żeby się już się nie przecinały to już trudniejsze zadanie... pisałem dlaczego.
Krzysiek K.
Feb 26, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Cytat:
Podpodział polega na tym, że ścieżki o dowolnej długości możemy zredukować do pojedynczej krawędzi;

Przez całe studia nie słyzsałem o czyms takim, jak podpodział grafu. Słyszałem za to o czymś takim jak homeomorfizm. Można więc powiedzieć, że graf jest planarny wtedy i tylko wtedy, jezeli nie zawiera podgrafu homeomorficznego z K5 bądź z K3,3. :)
thyros
Feb 26, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Wlasnie przeszedlem poziom 13.

Cytat:
Najbardziej wkurza brak mozliwości zaznaczania kilku na raz, obrotu już skonstruowanego układu... punkt po punkcie trzeba przesuwać, obracać...

Tez to zauwazylem, moze bedzie v2.

Skupiam sie raczej na poligonach niz na samych wierzcholkach. Wiec gdybysmy zrobili liste poligonow na podstawie grafu rozwiazanie byloby dosc proste: wystarczy polaczyc sciany wszystkich sasiadujacych ze soba poligonow.

Teraz pozostaje jak stworzyc liste poligonow i decydowac ktore z nich maja wspolne sciany.
Ale to juz zostawiam na przyszly tydzien.

Do uslyszenia

Krzysiek K.
Feb 27, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Cytat:
Skupiam sie raczej na poligonach niz na samych wierzcholkach. Wiec gdybysmy zrobili liste poligonow na podstawie grafu rozwiazanie byloby dosc proste: wystarczy polaczyc sciany wszystkich sasiadujacych ze soba poligonow.

A jak definiujesz poligon w grafie? :)
RageX
Feb 27, 2010

Odp: Teoria grafow czyli jak go rozsuplac

Chyba jakimś diagramem voronoi można by to wyliczyć - wyznaczyć...
A odpaliłem sobie 25 lvl... komp ledwo kwiczy.
Strony:
1 2