Matematické Fórum

Archiv diskusního fóra o matematice, 2006–2026

Toto je archiv Matematického Fóra. Fórum je dostupné jen ke čtení. Můžete se ale zaregistrovat na náš Discord server.

#1 28. 02. 2022 11:48

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

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: 5578
Reputace:   106 
 

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...


"Máte úhel beta." "No to nemám."

Offline

 

Archiv Matematického Fóra · stav k 30. 8. 2026 · 633 258 příspěvků v 108 818 tématech