Matematické Fórum

dash · 17. 10. 2015 18:58

Zdravím.

Zasekol som sa na jednej domácej úlohe a mám podozrenie, že ide buď o chybu v zadaní alebo o moje nepochopenie problému.

Ide o úlohu 5b:

//forum.matweb.cz/upload3/img/2015-10/00855_Screen%2BShot%2B2015-10-17%2Bat%2B18.51.10.png

1) Nie je mi jasné načo sa tam zavádza množina C, keď už nie je ďalej nikde použitá.
2) Protipríklad, pre ktorý si myslím, že tvrdenie neplatí. Maximálne pokrytie $M=\{\{1,5\},\{2,4\}\}$ . V grafe existuje cesta $x - 5 - 2 - y$ , žiadna z hrán tejto cesty nepatrí do množiny M.

//forum.matweb.cz/upload3/img/2015-10/00871_5.png

Ďakujem.

misaH · 17. 10. 2015 19:14

↑ dash:

Máš ukázať, že existuje množina (nazvali ju C) s nejakou vlastnosťou.

byk7 · 17. 10. 2015 19:18

Ahoj,

1) Ono je zvykem si množiny pojmenovávat, tak asi kvůli tomu. :-) (Předpokládám, že ve vzorovém řešení se budou odvoláváat právě na "množinu C" a ne na "podmnožinu množiny E\M".)

2) Domnívám se, že to může být tím, že 'M' není určeno jednoznačně. Pokud si vezmeš $M=\{\{1,5\},\{2,y\}\}$ , pak už tvrzení platit bude. Já osobně bych do zadání dodal ještě $C\subseteq E\setminus M\text{ (for some }M\text{) such that etc.}$ .

dash · 17. 10. 2015 19:29

↑ byk7: Stále mi to nie je jasné. Maximálne pokrytie predsa nemusí byť jednoznačné. Mojou úlohou je dokázať, že pre daný graf a dané pokrytie existuje množina C. Môžeš mi dať príklad množiny C na grafe a pokrytí, ktorý som uviedol?

dash · 19. 10. 2015 10:34

Viete mi prosím niekto poradiť? Mám s tým otravovať profesora, alebo je to moje nepochopenie úlohy?

Matematické Fórum

#1 17. 10. 2015 18:58

Bipartitný graf (chyba v zadaní?)

#2 17. 10. 2015 19:14

Re: Bipartitný graf (chyba v zadaní?)

#3 17. 10. 2015 19:18

Re: Bipartitný graf (chyba v zadaní?)

#4 17. 10. 2015 19:29

Re: Bipartitný graf (chyba v zadaní?)

#5 19. 10. 2015 10:34

Re: Bipartitný graf (chyba v zadaní?)

Zápatí