W dniu środa, 17 października 2012 01:38:32 UTC+2 użytkownik PK napisał:

> a) o cyklach długości max 1 (porządek słaby - z nieostrą relacją),
Coś mnie jeszcze niepokoi :) Czy chodzi o to, że jeden wierzchołek
reprezentuje wiele elementów i ma (być może dodatkową) krawędź łączącą z
samym sobą? Np. w jednym wierzchołku są szlauchy o tej samej długości
(de facto, długość to węży to już porządek liniowy).

Pozdrawiam

do góry

W dniu 2012-10-17 03:46, M.M. pisze:
> W dniu środa, 17 października 2012 01:38:32 UTC+2 użytkownik PK napisał:
>
>> a) o cyklach długości max 1 (porządek słaby - z nieostrą relacją),
> Coś mnie jeszcze niepokoi :) Czy chodzi o to, że jeden wierzchołek
> reprezentuje wiele elementów i ma (być może dodatkową) krawędź łączącą z
> samym sobą? Np. w jednym wierzchołku są szlauchy o tej samej długości
> (de facto, długość to węży to już porządek liniowy).

Mieszasz porządek na zbiorze z posortowaniem
po jakiejś własności.

Element zbioru jest jeden.
To zresztą leży w definicji porządku (wypadałoby przeczytać;)
"jeżeli a>=b i b>=a to a=b"
a=b, to ten sam element.

Twój przykład z węzami to porządek nie na zbiorze węzy,
ale na zbiorze liczb.

"jeżeli f(a)>=f(b) i f(b)>=f(a) to f(a)=f(b)"

Ale z tego, że dwa węze maja tą samą długość nie winika,
że to ten sam wąż.

Elementami grafu, o którym mowa powyżej nie są węże.



Nie da się wprowadzić porzędku liniwego na zbiorze węży.
Możesz wprowadzić tam porządek częściowy. Elementy
tej samej długości będą nieporównywalne. Graf będzie ok.

Ale jak widać, takie podejście jest mało praktyczne ;-)

pzdr
bartekltg

do góry

W dniu środa, 17 października 2012 04:06:43 UTC+2 użytkownik bartekltg napisał:
> Element zbioru jest jeden.
> To zresztą leży w definicji porządku (wypadałoby przeczytać;)
> "jeżeli a>=b i b>=a to a=b"
> a=b, to ten sam element.
> Twój przykład z węzami to porządek nie na zbiorze węzy,
> ale na zbiorze liczb.
> Ale z tego, że dwa węze maja tą samą długość nie winika,
> że to ten sam wąż.
> Nie da się wprowadzić porzędku liniwego na zbiorze węży.
No tak.



> Możesz wprowadzić tam porządek częściowy. Elementy
> tej samej długości będą nieporównywalne. Graf będzie ok.
To czegoś nie kumam. Dlaczego nieporównywalne jeśli mają
długość i porównujemy po długości? Jak np. trzy
węże będą miały taką samą długość to cykl będzie miał też
długość trzy a nie jeden?

Np. graf z trzema węzłami A,B,C.
A jest osiągalne zarówno z B i C (no i z A)
B jest osiągalne zarówno z A i C (no i z B)
C jest osiągalne zarówno z A i B (no i z C)
Dlaczego długość cyklu ma być jeden, jeśli jeden wąż to
jeden wierzchołek?

Pozdrawiam

do góry

W dniu środa, 17 października 2012 04:06:43 UTC+2 użytkownik bartekltg napisał:
> Możesz wprowadzić tam porządek częściowy. Elementy
> tej samej długości będą nieporównywalne. Graf będzie ok.
> Ale jak widać, takie podejście jest mało praktyczne ;-)

A jakby zrobić tak?
https://rapidshare.com/files/351208603/szlauch.png
Mamy szlauchy A,B,C,D,E,F.

Z jednej strony mamy szlauchy z relacją jest dłuższy lub równy.
Z drugiej wierzchołki w grafie z relacją jest osiągalny.
Tyle że cykl wychodzi 4 a nie 1.

Pozdrawiam

do góry

W dniu 2012-10-17 04:41, M.M. pisze:
> W dniu środa, 17 października 2012 04:06:43 UTC+2 użytkownik bartekltg napisał:
>> Element zbioru jest jeden.
>> To zresztą leży w definicji porządku (wypadałoby przeczytać;)
>> "jeżeli a>=b i b>=a to a=b"
>> a=b, to ten sam element.
>> Twój przykład z węzami to porządek nie na zbiorze węzy,
>> ale na zbiorze liczb.
>> Ale z tego, że dwa węze maja tą samą długość nie winika,
>> że to ten sam wąż.
>> Nie da się wprowadzić porzędku liniwego na zbiorze węży.
> No tak.
>
>
>
>> Możesz wprowadzić tam porządek częściowy. Elementy
>> tej samej długości będą nieporównywalne. Graf będzie ok.
> To czegoś nie kumam. Dlaczego nieporównywalne jeśli mają
> długość i porównujemy po długości?

O, to. Porównujemy po długości. Elementami jest liczba
centymetrów, nie waż.

> Jak np. trzy
> węże będą miały taką samą długość to cykl będzie miał też
> długość trzy a nie jeden?

Możesz sobie zrobić taki graf. Ale nie będzie on
grafem odpowiadającym jakiemukolwiek porządkowi.
Porządek wymaga:
>> "jeżeli a>=b i b>=a to a=b"

Koniec.

pzdr
bartekltg

do góry

W dniu 2012-10-17 05:07, M.M. pisze:
> W dniu środa, 17 października 2012 04:06:43 UTC+2 użytkownik bartekltg napisał:
>> Możesz wprowadzić tam porządek częściowy. Elementy
>> tej samej długości będą nieporównywalne. Graf będzie ok.
>> Ale jak widać, takie podejście jest mało praktyczne ;-)
>
> A jakby zrobić tak?
> https://rapidshare.com/files/351208603/szlauch.png
> Mamy szlauchy A,B,C,D,E,F.
>
> Z jednej strony mamy szlauchy z relacją jest dłuższy lub równy.
> Z drugiej wierzchołki w grafie z relacją jest osiągalny.
> Tyle że cykl wychodzi 4 a nie 1.


No, ładny graf. Ale nie jest to porządek.

"jeżeli a>=b i b>=a to a=b".

Z definicjami matematycznymi nie ma się co kłócić.
Jak nam nie odpowiada, należy ją zmodyfikować
lub zbudować nową, ale nie wolno twierdzić, że to
nadal to samo;)


pzdr
bartekltg

do góry

W dniu środa, 17 października 2012 05:28:39 UTC+2 użytkownik bartekltg napisał:

> No, ładny graf. Ale nie jest to porządek.
> "jeżeli a>=b i b>=a to a=b".
> Z definicjami matematycznymi nie ma się co kłócić.
> Jak nam nie odpowiada, należy ją zmodyfikować
> lub zbudować nową, ale nie wolno twierdzić, że to
> nadal to samo;)

Nie kłócę się, tylko próbuję ogarnąć :)
Jeśli dobrze Cię zrozumiałem, to zapis a=b,
oznacza tutaj wręcz że a jest tożsame b, nie
tylko że a jest równe b pod względem jakiejś
cechy?

Wynikało by z tego, że jak mamy zbiór {a,b,c,d} i cechę
f(a)=1, f(b)=1, f(c)=2, f(d)=3, to nie
da się tego zbioru posortować, bo na
tej cesze nie da się wprowadzić porządku
liniowego. Jednak posortować się da, więc
nadal nic nie kumam :) Chyba już późno :)

do góry

On 2012-10-16, M.M. <m...@g...com> wrote:
> W dniu wtorek, 16 października 2012 20:55:00 UTC+2 użytkownik Stachu 'Dozzie' K.
napisał:
>> A kto ci naklamal, ze taka relacja to relacja czesciowego porzadku,
>> a tym bardziej porzadku liniowego?
> A mozesz mi zacytowac gdzie napisalem ze to jest relacja czesciowego
> porzadku albo porzadku liniowego?

Zastanawiałeś się, jak posortować obiekty przy użyciu tej relacji. Do
sortowania potrzebna jest relacja porządku, stąd mój wniosek.

--
Secunia non olet.
Stanislaw Klekot

do góry

W dniu środa, 17 października 2012 08:26:00 UTC+2 użytkownik Stachu 'Dozzie' K.
napisał:
> > A mozesz mi zacytowac gdzie napisalem ze to jest relacja czesciowego
> > porzadku albo porzadku liniowego?
>
> Zastanawiałeś się, jak posortować obiekty przy użyciu tej relacji. Do
> sortowania potrzebna jest relacja porządku, stąd mój wniosek.
Nie zastanawiałem się, bo to oczywiste że się nie da. Zwróć uwagę
że ja nigdzie nie napisałem że nie mają racji ani czegoś w tym stylu.
Pozdrawiam

do góry

W dniu 2012-10-17 05:44, M.M. pisze:
> W dniu środa, 17 października 2012 05:28:39 UTC+2 użytkownik bartekltg napisał:
>
>> No, ładny graf. Ale nie jest to porządek.
>> "jeżeli a>=b i b>=a to a=b".
>> Z definicjami matematycznymi nie ma się co kłócić.
>> Jak nam nie odpowiada, należy ją zmodyfikować
>> lub zbudować nową, ale nie wolno twierdzić, że to
>> nadal to samo;)
>
> Nie kłócę się, tylko próbuję ogarnąć :)
> Jeśli dobrze Cię zrozumiałem, to zapis a=b,
> oznacza tutaj wręcz że a jest tożsame b, nie
> tylko że a jest równe b pod względem jakiejś
> cechy?
>
> Wynikało by z tego, że jak mamy zbiór {a,b,c,d} i cechę
> f(a)=1, f(b)=1, f(c)=2, f(d)=3, to nie
> da się tego zbioru posortować, bo na
> tej cesze nie da się wprowadzić porządku
> liniowego. Jednak posortować się da, więc
> nadal nic nie kumam :) Chyba już późno :)

Ale zamiast czegoś takiego < : f(a) < f(b) używasz niejawnie
(w zależności od algorytmu sortującego) czegoś podobnego do
< : f(a) < f(b) dla f(a) != f(b)
i(a) < i(b) dla f(a) = f(b)
gdzie i(a) daje indeks elementu a w tablicy wejściowej

do góry