zadanie z domkami, gazem, pršdem i wodš
yurghi
instalacje (gaz, prad i woda) tak aby linie te sie nie przecinaly.
Trzeba to zrobic na kartce (tzn linie nie moga przechodzic pod soba,
ani nie moga przechodzic przez poszczegolne domki na wylot).
Czy to zadanie da sie rozwiazac ?
Mariusz £apiñski
Rozwazmy przestrzen R^3 i 3 trojkaty rownoboczne, ktore zawieraja
sie w plaszczyznie R^2 i te plaszczyzny sa rownolegle wzgledem siebie.
Wtedy w kazdym ze srodkow trojkata umieszczamy po jednym domku
mniej wiecej tak:
A'
/\ B'
/ \ /\ C'
/ \ / \ /\
/ A \ / \ / \
/________\ / B \ / \
A''' A'' /________\ / C \
B''' B'' /________\
C''' C''
A teraz niech wierzcholki A',B',C' oznaczja odpowiednio gaz,
wierzcholki A'',B'',C'' oznaczja odpowiednio prad i
wierzcholki A''',B''',C''' oznaczja odpowiednio wode.
Z kazdego z wierzcholkow trojkata jest poloczenie z danym domkiem,
czyli domek jest zaopatrywamy w gaz, prad i wode.
No to teraz wystarczy polaczycz ze soba wierzcholki A',B',C' i
wierzcholki A'',B'',C'' oraz wierzcholki A''',B''',C''' i to
jest rozwiazanie.
Z powazaniem,
Mariusz Łapiński
_____________________________________________________
_ _
| \ / |__ mailto:mari...@pbi.pl
| \_/ / / http://www.pbi.pl/~mariuszl/
| \ / /
| |\_/| |___ Podlaskie Biuro Internetowe
|_| |_____| http://www.pbi.pl
_____________________________________________________
--
Internetowe Forum Dyskusyjne - http://www.newsgate.pl
Marek Szyjewski
Zadanie to rozwiazal dawno temu prof. Kazimierz Kuratowski:
Graf (uklad punktow polaczonych lukami) daje sie umiescic na
plaszcyznie tak, zeby krawedzie (luki) sie nie przecinaly, wtedy i
tylko wtedy, gdy nie zawiera zadnego z dwoch podgrafow:
pierwszym jest graf z zadania szesc wierzcholkow w dwoch grupach po
trzy, kazdy z pierwszej grupy polaczony z kazdym z drugiej grupy;
drugim jest graf o pieciu wierzcholkach, polaczonych kazdy z kazdym.
Pierwszy nazywa sie pelny graf dwudzielny 3x3 K_(3,3), drugi zas -
graf pelny o pieciu wierzcholkach K_5.
Dpwod twierdzeni Kuratowskiego jest trudny. Niepalanarnosc (niemoznosc
narysowania na plaszczyznie tak, zeby krawedzie sie nie przecinaly)
grafu K_(3,3) mozna uzasadnic tak: nazwimy droga ciag linii taki, ze
poczatek kazdej jest koncem nastepnej. W K_(3,3) dom A wystepuje w
nastepujacych drogach zamknietych: A-gaz-B-prad - A, A - prad -B woda
- A , A - gaz - B - woda A; i w jeszcze trzech z C w miejsce B;
podobnie B wystepuje w szesciu takich drogach i C tez. W kazdej drodze
sa dwa domy, wiec sumujac 6+6+6 = 18 liczymy kazda taka droge dwa
razy. Lacznie jest dziewiec drog zamknietych czworokatnych, ale z
kazdej trojki drog miedzy wszystkimi domami i dwoma zrodlami
instalacji obejscie jednej z nich to to samo, co obejscie pozostalych
dwoch po kolei. Czyli w ten sposob trzy drogi wyrazaja sie przez
pozostale. Podobnie bedzie jesli pogrupujemy drogi dla dwoch domow i
trzech zrodel - wiec zostaja trzy drogi niezalezne. Gdyby dalo sie to
narysowac na plaszczyznie - np. na kartce, to polozmy kartke na ziemi
i popatrzmy na rysunek jak na mape na globusie: trzy kraje + jeden na
zewnatrz rysunku - razem 4 kraje; dziewiec krawedzi i szesc
wierzcholkow. Stosujemy wzor Eulera:
s - k +w = 2,
4 - 9 + 6 = 1
a powinno wyjsc 2.
Okazuje sie, ze mozna umiescic graf K_(3,3) na torusie, ale nie ma
wtedy kraju zewnetrznego, a (wystarczy wykopac tunel w Ziemi, zeby
przeprowadzic ostatnia linie - kula z tunelem to topologicznie torus).
Jesli to kogos interesuje, to zliczajac minimalne drogi zamkniete
niezalezne, obliczalem pewna grupe homologii, czy jej range, a wiec
liczbe Bettiego...
Z powazaniem
Marek Szyjewski
My, samotnicy, powinnismy trzymac sie razem!
Marek Szyjewski
Mam takie dziwne wrazenie, ze jak podlaczysz prad i gaz do kazdego
domu i zlaczysz dostawy gazu ze soba, oraz dostawy pradu ze soba, to
powstanie lamana krzywa zamknieta i punkt A''' bedzie na zewnatrz tej
krzywej, a punkt C''' - wewnatrz. Z twierdzenia Jordana wiadomo, ze
krzywa zwyczajna zamknieta rozcina plaszczyzne na dwie czesci - nie
polaczysz A''' z C''' tak, zeby nie przeciac tej krzywej.
Szymon Wąsowicz
> Jasne
>
> Rozwazmy przestrzen R^3 i 3 trojkaty rownoboczne, ktore zawieraja
> sie w plaszczyznie R^2 i te plaszczyzny sa rownolegle wzgledem siebie.
>
> Wtedy w kazdym ze srodkow trojkata umieszczamy po jednym domku
> mniej wiecej tak:
> A'
> /\ B'
> / \ /\ C'
> / \ / \ /\
> / A \ / \ / \
> A''' A'' /_____\ / C \
> B''' B'' /_____\
> C''' C''
>
> A teraz niech wierzcholki A',B',C' oznaczja odpowiednio gaz,
> wierzcholki A'',B'',C'' oznaczja odpowiednio prad i
> wierzcholki A''',B''',C''' oznaczja odpowiednio wode.
> Z kazdego z wierzcholkow trojkata jest poloczenie z danym domkiem,
> czyli domek jest zaopatrywamy w gaz, prad i wode.
>
> No to teraz wystarczy polaczycz ze soba wierzcholki A',B',C' i
> wierzcholki A'',B'',C'' oraz wierzcholki A''',B''',C''' i to
> jest rozwiazanie.
>
> Z powazaniem,
>
Ale yurghi chciał na płaszczyźnie! A tam zadanie nie ma rozwiązania.
Rzecz sprowadza się do narysowania na płaszczyźnie grafu K_{3,3}.
Ale tego się nie da zrobić. Ten graf jest sztandarowym przykładem
grafu nieplanarnego. Zobacz np. w książce R. J. Wilsona "Wprowadzenie
do teorii grafów", strony 32 (rysunek K_{3,3}) i 83 (Tw. 12.1). Natomiast
w R^3 można zrobić wszystko: jest twierdzenie mówiące, że każdy graf
można narysować w R^3. I wcale nie trzeba trójkątów. Wystarczy, jak
pisze yurghi, przepuścić jedną linię nad inną (tylko jeden raz).
Serdecznie pozdrawiam,
Szymek