Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 10. 02. 2016 16:58

Katsushiro
Místo: Rožnov pod Radhoštěm
Příspěvky: 144
Škola: VŠB TUO - FEI
Pozice: student
Reputace:   
 

Matroid - důkaz

Ahoj všichni!

Narazil jsem na následující důkazovou úlohu:

Dokažte, že lesy na grafu (podgrafy neorientovaného grafu, které neobsahují cyklus) splňují [jakožto množiny hran] axiomy I1,I2,I3; speciálně jde o I3, tedy o fakt, že když les F1 má více hran než F2, tak lze jednu hranu z F1, která není v F2, přidat k F2, aniž v něm vznikne cyklus.

Důkaz se evidentně týká matroidu a jeho axiomů. Chápu to tedy jako matroid M(E,I), kde E je množina všech hran grafu a I je množina všech nezávislých podmnožin E.

Axiomy pro množinu I jsou:
1) $\emptyset \subset E$
2) $\left(x \subseteq X\right) \wedge (X \in I) \Rightarrow  (x \subseteq I)$
3) $(X,Y \in I) \wedge (||X|| < ||Y||) \Rightarrow \exists y \in (Y \setminus X): X \cup \{y\} \in I$

Vůbec ale netuším, jak dokázat, že to obecně platí.

Mohli byste mi, prosím, napovědět? :-)

Moc děkuji za všechny odpovědi,
Katsu

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson