On Fri, 24 Feb 2012 00:14:55 +0100, Piotr Chamera
<p...@p...onet.pl> wrote:

>W dniu 2012-02-23 20:23, A.L. pisze:
>> On Thu, 23 Feb 2012 11:47:26 +0100, Piotr Chamera
>> <p...@p...onet.pl> wrote:
>>
>>> W dniu 2012-02-23 00:24, n...@m...invalid pisze:
>>>>>> 2. Znakujemy węzły rosnąco liczbami wymiernymi wg kolejności w
>>>>>> wyjściowym porządku (to można zrobić raz dla wielu kolejnych
>>>>>> przekształceń, może być potrzeba dokładnej arytmetyki).
>>>> 1: 1/2; 2: 2/3; 3: 3/4; ... ? Co to daje, mogę prosić o objaśnienie?
>>>
>>> Jeszcze wyjaśnienie dlaczego pisałem o liczbach wymiernych - pomiędzy
>>> dwie dowolne liczby wymierne można zawsze wstawić trzecią, co w tym
>>> przypadku pozwala nie dotykać znakowania wierzchołków, których nie
>>> przesuwamy.
>>
>> To jest mniej wiecej tak jak ja robie i nazywam "brute force"
>
>Może coś mylę, ale:
>
>zakładam, że graf się nie zmienia, zmieniamy tylko porządek,
>więc zbiory poprzedników i następników danego węzła w grafie
>są również stałe - można je wyliczyć i zapisać w jakiejś strukturze
>dowiązanej do każdego węzła.
>
>> Jak wezly A B C D przeorganizujemy
>
>załóżmy znakowanie w jakimś początkowym porządku topologicznym
>od lewej do prawej
>
>(A 1) (B 2) (C 3) (D 4)
>
>jeśli mamy porządek topologiczny, to wszystkie krawędzie wchodzące do
>danego węzła X muszą wychodzić z węzłów o znakowaniach mniejszych niż
>znakowanie przypisane do X a wychodzące muszą prowadzić do węzłów o
>znakowaniach większych niż to przypisane do X.
>
>> na B A D C, to tzreba sprawdzic ze
>
>zmieniamy kolejność i znakowanie tak:
>D przesunęliśmy między B i C więc dostał znakowanie mniejsze od C i
>większe od B, B przestawiliśmy przed A, który był pierwszy w początkowym
>porządku, więc B więc dostał dowolne znakowanie mniejsze od A.
>
>(B 1/2) (A 1) (D 5/4) (C 3)
>
>wystarczy sprawdzić, czy wszystkie krawędzie grafu wchodzące do (B 1/2)
>są z nadal z węzłów o znakowaniu mniejszym od obecnego znakowania
>węzła B i wszystkie wychodzące z B nadal prowadzą do węzłów o znakowaniu
>większym od znakowania węzła B. I analogicznie dla węzła D.
>
>Dla każdego przesuwanego węzła mamy k_we + k_wy sprawdzeń (porównań
>liczb, k_we - liczba krawędzi wchodzących do węzła, k_wy - liczba
>krawędzi wychodzących z węzła).
>
>> A D C sa w zbiorze nastepnikow B, a BAD jes tw zbiorze poprednikow C i
>> tak dalej.
>Powyżej piszę o następnikach i poprzednikach w grafie, a nie w porządku.
>Węzły zawsze są oznakowane rosnąco, zgodnie z porządkiem wyjściowym, a
>po zmianie - testowanym. Jeżeli po zmianie zaburzyliśmy porządek,
>to dla któregoś z przesuniętych węzłów X w zbiorze jego poprzedników w
>grafie znajdzie się węzeł o znakowaniu większym niż jego własne lub w
>zbiorze następników w grafie znajdzie się węzeł o znakowaniu mniejszym
>niż jego własne.
>
>> Wle to nie wystarcza, bo oprocz amiany uporatdkowania moze byc
>> przesuniecie, na przykald A moze byc przesuniety z pozycji 100 na
>> pozycje 50. Moze wtedy "wypasc" ze zbioru nastepnilkow wezlow miedzy
>> 50 a 99, wiec te wezly tzreba sprawdzic.
>Tak, ale nie interesują nas te, z których nie było bezpośredniej
>krawędzi do A, więc jeśli znamy węzły, z których mamy w grafie
>bezpośrednie przejście do A (a ten zbiór dla każdego węzła możemy
>wyliczyć i zapamiętać raz, na początku, gdyż graf się nie zmienia),
>to możemy je łatwo sprawdzić.
>
>Jeśli A przeskoczyło jakiś węzeł X, który w grafie był jego
>poprzednikiem, to będzie miało teraz mniejsze od niego znakowanie -
>jeśli sprawdzimy listę poprzedników A w grafie, to znajdziemy tam teraz
>węzeł X o znakowaniu większym niż A, a pamiętamy, że wszystkie
>poprzedniki powinny mieć znakowanie mniejsze niż A - da nam to
>informację, że krawędź prowadząca z X do A zmieniła kierunek
>i zaburzyliśmy porządek.
>
>Podobnie jahk D soztanie
>> pzresyniety z pozycji 100 na pozycje 200, to moze wypasc ze zbioru
>> poprzednikow, wiec trzeba sprawdzic wezly od 100 do 200.
>>
>> Troche dzuo tych sprawdzen, i pytanie - czy nie mozna mniej?...
>>
>> A.L.
>
>Może w tym co piszę wyżej jest jakaś luka lub błąd, albo źle
>zrozumiałem zadanie, jeśli tak, to proszę o jakiś prosty kontrprzykład
>do analizy.

Musze pzreczytac i sie zastanowic. Co uczynie w weekend :)

A.L.