Teoria grafow czyli jak go rozsuplac

[thyros]

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]

Musi być planarny.

[Xion]

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]

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

...tak, że jego krawędzie się nie przecinają

[RageX]

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]

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

[thyros]

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]

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

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

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

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

[nilphilus]

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]

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]

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

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)



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

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]

Wlasnie przeszedlem poziom 13.

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

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?