Matematické Fórum

Kondr · 03. 12. 2009 22:15

↑↑ elnino:Pokud Trg(n) značí množinu Trianglií na n vrcholech, máme dokázat, že
$\forall n\in \mathbb{N}.\forall G\in Trg(n).\text{princ se vrati v grafu }G$
(to jsem chtěl říct svým příspěvkem)
Využít Petersonův trojúhelník znamená dokazovat daleko slabší podmínku:
$\exists n\in \mathbb{N}.\exists G\in Trg(n).\text{princ se vrati v grafu }G$
Ve svém příspěvku ↑↑ petrkovar: ukazuje, že $Trg(2n)=\emptyset$ , takže stačí dokázat, že
$\forall n\in \mathbb{N}.\forall G\in Trg(2n).\text{princ se vrati v grafu }G$
Navíc vysvětluje, že touto úvahou se samotný postup nezkrátí.

elnino · 04. 12. 2009 22:03 — Editoval elnino (04. 12. 2009 22:35)

↑ Kondr:Ja som dokazal ze graf musi mat sudy pocet vrchom aby bol konecny ale to nic nieje, to viem. Potrebujem zistit ci sa vrati domov. Ci sa bude nejaky sled opakovat. Ale dokazat to neviem.Mozem to dokazat pomocou Hamiltonovskeho sledu ale ten zas neni u vsetkych konecnych grafov.

Kondr · 04. 12. 2009 23:01

↑ elnino:Hamiltonovský sled tam není, navíc princ může jednou hranou projít i vícekrát. Použitím hintu ze zadání a mého hintu zde: ↑↑ Kondr: vy to mělo být snadné.

elnino · 05. 12. 2009 06:55 — Editoval elnino (05. 12. 2009 07:03)

↑ Kondr:
Praveze ho neviem pouzit. Trocha mu nechapem:(((
A najviac v Hamiltonovskom slede moze prejst hranu viackrat to v Hamiltonovskom cykle sa nesmie prejst hrana vickrat.

petrkovar · 05. 12. 2009 10:33

↑ elnino:Pojem "Hamiltonovský sled" je spíš zavádějící. V hamiltonovském cyklu nebo cestě (které jsem jen zmínil v bonusu na přednášce) se
- nesmí opakovat vrcholy --- ale ve sledu ano (tak proč sled?)
- musí projít všechny vrcholy grafu - ale v Trianglii ne (tak proč hamiltonovský)
(navíc malé "h", když je hamiltonovský. Kdyby byl Hamiltonův, tak velké H)

Nefunguje mi Kondrův odkaz na hint, tak neumím zareagovat na to, čemu není rozumět. Pravdou je, že všechny důležité části tady byly řečeny. Teď jde o to je správně poskládat dohromady.
Nápověda 1: Zkuste si nakreslit jeden příklad (všimněte si, že nemusí být rovinný, v Trianglii mohou být mosty!). Nakreslete si palác k jedné hraně. Zkuste grafem putovat jak princ podle pravidel. Vrátíte se? Pokud toto udělá 15 studentů, každý se svým grafem, (nebo méně lidí s více grafy) a napíše, zda se vrátil zpátky a jestli si něčeho nevšiml, tak tu může vzniknout zajímavý přehled, který něco napoví.
Nápověda 2: Nemusí to být pro každého ten nejvhodnější postup, pokud máte nakročeno jinak.

Autor skryl část textu. Zobrazit/skrýt!

Kondr · 05. 12. 2009 20:30

Tak jsem byl mimoběžným kanálem požádán o pomoc s touto úlohou, nadhodím ještě jednu myšlenku, která se mi líbí: místo cest zavedeme dálnice -- tedy vždy dva oddělené pruhy. Pro každou hranu pevně zvolíme barvy pruhů, jeden bude modrý a druhý zelený. Jednotlivé křižovatky nyní budou mimoúrovňová křížení -- zelený pruh vždy zatáčí doleva a napojuje se na modrý, modrý zatáčí doprava a napojuje se na zelený. Takto princ nemá jinou možnost než se držet způsobu zatáčení, který slíbil. Silniční síť se nám takto rozpadla na několik kusů. Zůstane princ stále ve stejném kusu? Projede ho celý? Na odpovědi na tyto otázky si musí milovníci pohádek počkat do příštích vánoc. A nebo na ně přijít sami ;)

Přišlo mi to jako zajímavý pohled na úlohu, ale dost možná je to v očích ctěného čtenářstva velmi zákeřný návod.

elnino · 05. 12. 2009 22:55 — Editoval elnino (05. 12. 2009 23:05)

Uz to mam aleluja. Dakujem za rady
Pre kontrolu ci som si dobre vsimol. Zdvojim hrany.......

osel · 06. 12. 2009 09:51

↑ elnino: A jak to teda dopadlo? Vrati se Princ zpatky do sveho palace? A jak si napsal dukaz? To by me velice zajimalo ;-)

Matematické Fórum

#26 03. 12. 2009 22:15

Re: teorie grafu s princem

#27 04. 12. 2009 22:03 — Editoval elnino (04. 12. 2009 22:35)

Re: teorie grafu s princem

#28 04. 12. 2009 23:01

Re: teorie grafu s princem

#29 05. 12. 2009 06:55 — Editoval elnino (05. 12. 2009 07:03)

Re: teorie grafu s princem

#30 05. 12. 2009 10:33

Re: teorie grafu s princem

#31 05. 12. 2009 20:30

Re: teorie grafu s princem

#32 05. 12. 2009 22:55 — Editoval elnino (05. 12. 2009 23:05)

Re: teorie grafu s princem

#33 06. 12. 2009 09:51

Re: teorie grafu s princem

Zápatí