Matematické Fórum

Pavel Brožek

Ahoj,

řeším cvičení z diskrétní matematiky (Matoušek, Nešetřil: Kapitoly z diskrétní matematiky, str. 59):

Ve výsledcích na konci knihy není k tomuto cvičení nic napsáno. Přijde mi, že to tvrzení není pravdivé, že doplněk není tranzitivní relace. Vezměme si např. permutaci $\pi=(1\, 3\, 2)$ . Jediná dvojice $(i,j)$ , která je inverzí, je $(2,3)$ , tedy $I(\pi)=\{(2,3)\}$ . Doplněk této relace je $(\{1,2,3\}\times\{1,2,3\})\setminus I(\pi)=\{(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(3,2),(3,3)\}$ . Do doplňku tedy patří $(2,1)$ a $(1,3)$ . Kdyby doplněk byl tranzitivní relace, muselo by tam patřit i $(2,3)$ , to tam ale nepatří.

Dělám někde chybu já, nebo je chyba v knize?

jarrro · 10. 11. 2012 15:28

nemyslia doplnok v relácii kde sú len dvojice pre ktoré je i<j ?
potom ak $$i,j$, $j,k$$ patria do toho doplnku tak
$i<j<k \wedge \pi{$i$}<\pi{$j$}<\pi{$k$}$

Pavel Brožek

↑ jarrro:

Aha, no asi budeš mít pravdu, když se z doplňku vezmou pouze takové dvojice $(i,j)$ , kde $i< j$ , pak je to skutečně tranzitivní relace. Ale přijde mi teda, že je to pak blbě zadané. Díky.

Andrejka3 · 10. 11. 2012 17:53

V knize je též adresa na stránku, kde jsou opravy. Je tam i opravené zadání tohoto příkladu. Nemám ji u sebe, tak nemohu odkázat.

Pavel Brožek · 10. 11. 2012 18:06

↑ Andrejka3:

Vím o této stránce, tam jsem se díval a opravu jsem nenašel, proto jsem psal sem.

Andrejka3 · 10. 11. 2012 18:16

↑ Pavel Brožek:
Aha, tehdy jsem příklad řešila z knihy černé barvy, myslím druhé vydání, kde to bylo jinak zadané (špatně) než v oranžovém vydání (asi čtvrtém). Až budu mít možnost, můžu se podívat, jak zadání změnili.

Pavel Brožek · 10. 11. 2012 18:19

↑ Andrejka3:

Díky, ale není potřeba. Stačí mi, že jsem já nic nepřehlédl.

Matematické Fórum

#1 10. 11. 2012 14:48 — Editoval Pavel Brožek (10. 11. 2012 14:53)

Tranzitivita doplňku relace inverzí v permutaci

#2 10. 11. 2012 15:28

Re: Tranzitivita doplňku relace inverzí v permutaci

#3 10. 11. 2012 15:34 — Editoval Pavel Brožek (10. 11. 2012 15:34)

Re: Tranzitivita doplňku relace inverzí v permutaci

#4 10. 11. 2012 17:53

Re: Tranzitivita doplňku relace inverzí v permutaci

#5 10. 11. 2012 18:06

Re: Tranzitivita doplňku relace inverzí v permutaci

#6 10. 11. 2012 18:16

Re: Tranzitivita doplňku relace inverzí v permutaci

#7 10. 11. 2012 18:19

Re: Tranzitivita doplňku relace inverzí v permutaci

Zápatí