Wikipédia

„Matroidaxiómák” változatai közötti eltérés

Laptörténet interaktív böngészése
[nem ellenőrzött változat][nem ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Pasztillabot (vitalap | szerkesztései)
botok
116 360 szerkesztés
a Rendezés a gondolatjelek körül
Cherybot (vitalap | szerkesztései)
51 479 szerkesztés
a Robot: Szomszédos írásjelek kurziválása
32. sor:
{| border=1 cellspacing=0
|- align=left
|| B1. || ''nem-üresség:'': || <math>\mathcal{F} \ne \empty </math>;
|- align=left
|| B2. || ''leszállóság:'': || <math> \forall X,Y \! \in \! \mathcal{P}(U) : \; \left[ \ \left( X \subseteq Y \ \wedge \ Y \! \in \! \mathcal{F} \right) \ \Rightarrow \ X \! \in \! \mathcal{F} \ \right] </math>
|- align=left
|| B3. || ''kölcsönös bővíthetőség:'': || <math> \forall K,N \! \in \! \mathcal{F} : </math> <math> \; \left[ \ \left| K \right| < \left| N \right| \ \Rightarrow \ \exist x \! \in N \! - \! K : \ \left( K \cup \left\{ x \right\} \in \mathcal{F} \right) \ \right] </math>
|}
 
Megjegyzés: a harmadik axiómát, talán elnevezési/fordítási hiba vagy tanácstalanság miatt vagy más okból, „''kölcsönös„kölcsönös felcserélhetőségi axiómánakaxiómának”''” is nevezik (ld. ''[[#Források|Cormen-Leiserson-Rivest-Stein: Új algoritmusok 346. o.]]'')
 
=== Halmaz bővítője és maximális függetlensége ===
53. sor:
== A maximalitási axiómarendszer és a rang ==
 
Az előkelő „maximalitási” szó arra utal, hogy a nem bővíthető független (''(maximális független)'') halmazok számossága ugyanaz.
 
{| border=1 cellspacing=0
|- align=left
|| 1. || ''nem-üresség:'': || <math>\mathcal{F} \ne \empty </math>;
|- align=left
|| 2. || ''leszállóság:'': || <math> \forall X,Y \! \in \! \mathcal{P}(U) : \; \left[ \ \left( X \subseteq Y \ \wedge \ Y \! \in \! \mathcal{F} \right) \ \Rightarrow \ X \! \in \! \mathcal{F} \ \right] </math>
|- align=left
|| 3. || ''maximalitási tulajdonság:'': || <math> \forall X \! \in \! \mathcal{P} \! \left( U \right) : \ \forall F,G \! \in \! \mathcal{F} \cap \mathcal{P}(X): </math> <center> <math> \left[ \ \left( \ \exist x \! \in \! X: \ F \cup \left\{ x \right\} \not\in \mathcal{F} \ \right) \Rightarrow \left| F \right| = \left| G \right| \ \right] </math> </center>
|}
 
76. sor:
 
Belátjuk, hogy a bővíthetőségi tulajdonságból következik a maximalitási, ill. fordítva.
* Legyen <math> \left( U , \mathcal{F} \right) </math> bővíthetőségi tulajdonsággal rendelkező nem, üres leszálló halmazrendszer. Legyen <math> M,N \subseteq X </math> két ''maximális'' („nem bővíthető”) független halmaz X-ben. Ha az egyik szigorúan kisebb számosságú lenne, mint a másik, mondjuk <math> \left| M \right| < \left| N \right| </math> lenne ([[indirekt bizonyítás]]), akkor ez ellentmondana a bővíthetőségi tulajdonságnak, hiszen feltevéseinkből adódóan ''biztos,'', hogy van olyan <math> x \in N-M </math>, amelyre <math> M \cup \left\{ x \right\} \in \mathcal{F} </math> független, de mivel <math> x \not\in M </math> és M véges (mivel az alaphalmaz is véges), ezért <math> M \subset M \cup \{ x \} </math>, ami ellentmond annak, hogy maximális, azaz nem bőívíthető. Tehát (< trichotom tulajdonsága miatt) bármely két maximális független halmaz azonos számosságú, tetszőleges <math> X \subseteq U </math> esetén.
* Legyen <math> \left( U , \mathcal{F} \right) </math> izokardinalitási tulajdonsággal rendelkező halmazrendszer. Legyen ekkor <math> K,N </math> két független halmaz úgy, hogy <math> \left| K \right| < \left| N \right| </math>. Ekkor <math> K </math> nem lehet maximális független halmaz az <math> N \cup K \subseteq U </math> (nem felt. független) részhalmazban, mert az ellentmondana annak, hogy az ilyenek egyenlő számosságúak, hiszen van egy nála nagyobb számosságú független részhalmaz (<math> N </math>). Tehát van olyan <math> x \in K \cup N , x \not\in K </math> elem, hogy ezzel bővítve <math> K </math>-t független halmazt kapjunk. Egyszóval <math> \left( K \cup N \right) - K = N-K </math> -beli, mert könnyen láthatóan e két halmaz egyenlő, így tehát <math> K </math> bővíthető egy <math> N </math> -beli elemmel, és pont ezt akartuk belátni.
 
98. sor:
 
== Források ==
* ''Cormen'' – ''Leiserson'' – ''Rivest'' – ''Stein:'': ''''' Új algoritmusok '''''. Scolar Kiadó, Bp., 2003. ISBN 9639193909
* ''Frank András:'': [http://www.cs.elte.hu/~frank/jegyzet/matroid/ (jegyzetek)] ''[http://www.cs.elte.hu/~frank/jegyzet/matroid/ulmat.2004.ps Matroidelmélet jegyzet (Post Script)].''.
 
[[Kategória:Kombinatorika]]
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Matroidaxiómák”