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
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
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 28. 02. 2022 11:48

M___A
Zelenáč
Příspěvky: 3
Škola: UK
Pozice: student
Reputace:   
 

Teorie grafu - párování faktorových podgrafů

Dobrý den,

dokázal by mi někdo poradit, jak postupovat při určování správného řešení?


Nechť M je párování v souvislém grafu G.
Dokažte, že existuje kostra T grafu G, pro které platí M ⊆ E (T).

Předem děkuji
M

Offline

 

#2 28. 02. 2022 20:35

check_drummer
Příspěvky: 3528
Reputace:   91 
 

Re: Teorie grafu - párování faktorových podgrafů

Ahoj,
co použít algoritmus hledání minimální kostry? Hranám z párování dám malou váhu, ostatním obrovskou. A lze ukázat, že hladový algoritmus zafunguje...


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson