Zagadnienie literackie

Ktoś czytał "Rękopis znaleziony w Saragossie" Potockiego? Zakładam, że film Hassa na motywach tejże powieści oglądał każdy (jest ponoć kultowy również poza Polską, pieniądze na restaurację i koloryzację filmu wyłożył M. Scorsese). OK, to nie odpytywanie z lektury, chodzi mi tylko o to by przypomnieć specyficzną konstrukcję owej powieści, (widzowie filmu mieli okazję poczuć jak to jest zrobione, ale w stopniu komplikacji film nie zbliża się nawet do książkowego oryginału). Jest owa konstrukcja mianowicie taka - pomysł zbieżny z wschodnimi "Baśniami tysiąca i jednej nocy" - mamy opowieść główną i głównego narratora, który przeżywając swoje przygody napotyka inne postaci, które opowiadają mu własne przygody (co narrator przytacza dosłownie więc narracja zawsze pozostaje narracją w pierwszej osobie), w tych opowieściach rekurencyjnie zaczynają się i kończą inne opowieści i tak dalej, przy czym "głębokość stosu" o ile mnie pamięć nie zawodzi sięga w najgłębszym miejscu czterech. To nie koniec, zdarza się, że poszczególne opowieści odwołują się do tych samych postaci i wydarzeń, mają wspólnych bohaterów i/lub są dobrze zlokalizowane w czasie względem wydarzeń historycznych.
Nie sporządziłem czytając, choć kusiło mnie niezmiernie i może kiedyś to zrobię, diagramu wszystkich tych opowieści. Gdyby miał powstać należałoby zrobić coś takiego:

-Wypisać wszystkie wydarzenia (zakładając upraszczająco ich punktowość w czasie) jakie miały miejsce do których odwołują się poszczególne opowieści.

-Wprowadzić relację późniejsze/wcześniejsze pomiędzy wydarzeniami w oparciu o:
a) następstwo chronologiczne wydarzeń wewnątrz opowieści.
b) fakt, że opowiadane są wydarzenia przeszłe w więc miały miejsce przed zdarzeniem polegającym na rozpoczęciu opowiadania
c) następstwo czasu względem wydarzeń historycznych wspomnianych w opowieściach
d) informacje o wieku bohaterów w opowieści w poszczególnych opowieściach
e) inne, które nie przyszły mi teraz do głowy

Teraz załóżmy że zaznaczymy sobie zdarzenia kropkami a fakt następowania zdarzeń po sobie oznaczymy strzałką skierowaną od zdarzenia wcześniejszego do późniejszego.
To co powinniśmy dostać - o ile Potocki sprytnie nie oszukał nas gdzieś (chcący), bądź nie popełnił złośliwego i niezauważanego przez jego samego i czytelników błędu (niechcący w tym wypadku) - to tzw. DAG (czyli Directed Acyclic Graph - skierowany graf bez cykli).
Właściwie, wysycając do końca informacje z punków a-e, powinniśmy uzyskać coś więcej, mianowicie graf reprezentujący silny porządek częściowy. To wysycenie sprowadza się do prostej uwagi, że następstwo w czasie jest relacją przechodnią (bardziej uczenie i z obca: tranzytywną), czyli jeżeli zdarzenie B następuje po zdarzeniu A a zdarzenie C po zdarzeniu B to zdarzenie C następuje po zdarzeniu A.
Sekunda na definicje:

DAG jest to para składająca się ze zbioru wierzchołków V i relacji R ⊆ VxV t.że dla każdego ∀a1...∀an t. że (ai,ai+1) ∈ R dla i = 1,...,n mamy a1 ≠ an

Porządek częściowy w zbiorze A jest to relacja R ⊆ AxA, która jest

1. zwrotna tzn. ∀ a (a,a) ∈ R
2. antysymetryczna tzn. (a,b) ∈ R i (b,a) ∈ R ⇒ a = b
3. przechodnia tzn. ∀ a b c (a,b) ∈ R i (b, c) ∈ R ⇒ (a,c) ∈ R

Nasz porządek wydarzeń w "Rękopisie" nazwałem "silnym porządkiem częściowym" co sprowadza się do tego, że modyfikujemy powyższą definicję i punkty 1 i 2 zastępujemy punktem:
1' antysymetryczna tzn ∀ a (a,a) ∉ R'

Mimo, że żaden porządek częściowy nie śmie być silnym porządkiem częściowym i vice versa (co przy okazji ilustruje nieco paradoksalne zjawisko semantyczne, że znaczenie rzeczownika z przymiotnikiem może nie mieścić się w zakresie znaczenia samego rzeczownika), to chwila zastanowienia pozwala stwierdzić, że są te relacje dobrymi krewnymi. Mianowicie (proste ćwiczenie) uzupełniając silny porządek R' o relację identyczności I = {(a,a), a \in A} dostajemy porządek częściowy, tzn R = R' ∪ I jest porządkiem częściowym. Podobnież, odejmując I od porządku R dostaniemy silny porządek częściowy (R'=R\I jest silnym porządkiem częściowym).

Dla pełnej konsystencji, wysycenie o którym wspomniałem w języku porządków sprowadza się do, nazwijmy to szumnie, twierdzenia:
Niech dany będzie DAG (A,R). Zdefiniujmy R'' = R ∪ RR ∪ RRR ∪ ... gdzie napisanie relacji jedna po drugiej oznacza operację ich złożenia. Wówczas (A, R'') jest silnym porządkiem częściowym. W fachowej nomenklaturze R'' nazywa się domknięciem tranzytywnym R. Częściej niż ja to zrobiłem tutaj, i dając lepsze konotacje nazwie "domknięcie tranzytywne" definiuje się ją tak: ∏ {S | s relacja tranzytywna na A} a potem dowodzi, że R'' jest postaci takiej jaką podałem za definicję. Ale operować w myślach, dla zbiorów skończonych przynajmniej, łatwiej znacznie konstruktywnym opisem.


Wracając do naszego modelu. Dla ułatwienia, ponieważ porządki częściowe to to z czym w matematyce pracujemy częściej, w dalszym ciągu wywodu nasz silny porządek częściowy, opisanym wyżej sposobem, zmienimy na porządek częściowy. W naszym kontekście literackim oznacza to, że przyjmujemy założenie z którym łatwo się pogodzić, że każde zdarzenie jest jednoczesne z samym sobą.

OK, zadajmy więc arcyliterackie Pytanie: ile maksymalnie zdarzeń opisanych w powieści mogło rozgrywać się jednocześnie ?
I natychmiast strawestujmy je w języku relacji porządkujących w następujący sposób: mając porządek częściowy w zbiorze skończonym, znaleźć maksymalną możliwą liczbę elementów wśród których żadne dwa nie będą porównywalne. Nazwiemy to szerokością zbioru uporządkowanego.

Można zrobić to na wiele sposobów, z których najprostszy i najbardziej pracochłonny to dla każdego podzbioru zbioru A sprawdzić czy jego elementy są parami nieporównywalne, jeżeli tak zapisać liczność tego zbioru i z zapisanych liczb po przejrzeniu całości wybrać liczbę największą.

Proponuję sposób następujący. Najpierw znowu pooznaczam:

A - zbiór skończony, R - relacja częściowego porządku w A, dla a ∈ A R+(a) = {x| aRx} \ {a} , R-(a) = {x | xRa}\{a}

Zdefiniuję teraz:
łańcuchem w (A,R) nazywamy podzbiór A który jest liniowo uporządkowany względem relacji R zawężonej do niego

antyłańcuchem w (A,R) nazywamy podzbiór w A w którym żadne dwa różne lementy nie są porównywalne. Szerokość zbioru oznaczę przez SZ.

Twierdzę teraz, że:

∀ a SZ(A) = max(SZ(A \ (R+(a) ∪ {a})), SZ(A \ (R+(a) ∪ {a})), 1+SZ(A\(R+(a) ∪ R-(a) ∪ {a})))

Jest tak gdyż:
Dla dowolnego elementu a, jeżeli
Przypadek 1) a należy do pewnego antyłańcucha o maksymalnej liczności. Wtedy antyłańcuch ten zawiera się w A\(R+(a) ∪ R-(a)) - bo ma a jako swój element i nie zawiera żadnego elementu porównywalnego z a. Wystarczy więc znaleźć jakiś antyłańcuch maksymalnej liczności w A\(R+(a) ∪ R-(a) ∪ {a}) i dołączyć do niego a (bo do każdego "dobrego" podzbioru elementów tego zbioru możemy dołączyć a dostajac ciągle dobry zbiór). Jego moc wynosi więc 1+SZ(A\(R+(a) ∪ R-(a) ∪ {a})).
Jeżeli zaś
Przypadek 2) a nie należy do antyłańcucha o maksymalnej liczności. Wtedy to pewien taki antyłańcuch zawiera się w A \ (R+(a) ∪ {a}) lub A \ (R-(a) ∪ {a}) (bo nie zawiera a, i nie może jednocześnie zawierać elementu z R+(a) i R-(a))
Ostatecznie szukając maksymalnej liczności antyłańcucha można sprowadzić do poszukiwania w podzbiorach jak w tezie (+1 dla wyniku w zbiorze A\(R+(a) ∪ R-(a) ∪ {a})) ) i wyboru maksymalnej z tych liczb.

Twierdzenie to sprowadza nam poszukiwanie SZ(A) do wyboru dowolnego elementu a i powtórzenia procedury dla trzech istotnie mniejszych zbiorów a następnie scalenia wyników przy pomocy prostej arytmetyki sprowadzającej się do inkrementacji jednego z wyników i funkcji maximum. To gotowy algorytm rekurencyjny.
Arbitralność wyboru elementu a otwiera pewne perspektywy w ew. optymalizacji algorytmu, ale mniejsza o to.

Ćwiczone na zajęciach z algorytmiki, wykładach z matematyki dyskretnej lub kombinatoryki, względnie ogólnie zainteresowane oko zauważy pokrewieństwo serwowanego problemu z twierdzeniem znanym pod nazwą twierdzenie Dilwortha. Mówi ono mianowicie, że w zbiorze częściowo uporządkowanym liczność maksymalnego (w sensie inkluzji) antyłańcucha w jest równa minimalnej ilości rozłącznych łańcuchów, których suma daje cały zbiór. To jednak jak to mówią, zupełnie inna historia.

Ciekawe, czy na zajęciach dajmy na to z teorii literatury na polonistyce nietaktem byłoby zadać nasze Pytanie ?

Przy okazji, do rozważań nad owym problemem i algorytmem sprowokowało mnie nie literatura wcale, ale pewne zagadnienie dotyczące alokacji zasobów w sieci telekomunikacyjnej. Ale to naprawdę inna historia.