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 13. 01. 2013 20:15

hrubon
Zelenáč
Příspěvky: 10
Škola: MFF UK
Pozice: student - Bc.
Reputace:   
 

Indukovaný podgraf stromu je strom

Zdravím,
můžete mě, prosím, někdo kopnout do p***le a říct mi, co mi uníká?

Definice:
Strom je:
- souvislý graf
- neobsahující kružnice

Tvrzení:
neorientovaný graf G je strom =>
=> G-v je strom (tj. graf G bez jeho libovolného vrcholu v a všech hran, které do v vedou)

Mějme takovýto graf, který je strom:
http://s2.postimage.org/wouw3a009/tree.png
Když přeci odeberu vrchol v (na obrázku), tak se mi strom rozpadne na čtyři komponenty souvislosti a přestane být souvislý, tudíž to nemůže být strom, tak kde sakra dělám chybu, když mi to tvrzení v učebnici Matoušek, Neštřil předvádí důkazem?!

Offline

  • (téma jako vyřešené označil(a) hrubon)

#2 13. 01. 2013 20:57 — Editoval Brano (13. 01. 2013 21:02)

Brano
Příspěvky: 2673
Reputace:   232 
 

Re: Indukovaný podgraf stromu je strom

Nerobis nikde chybu. Ano ak utnes vrchol ktory nie je "list" (taky co donho vedie iba jedna hrana) tak sa ti graf rozpadne viac novych stromov. Pripadne si skontroluj ci v tej knihe neuvazuju ako stromy aj nesuvisle grafy bez kruznic, aj ked tie sa obvykle volaju "les".

A co presne tvrdia v tej knihe?

Offline

 

#3 13. 01. 2013 21:12

hrubon
Zelenáč
Příspěvky: 10
Škola: MFF UK
Pozice: student - Bc.
Reputace:   
 

Re: Indukovaný podgraf stromu je strom

↑ Brano:
Díky za ujištění jsem pako. V té knize je samozřejmě napsáno "V případě, že v je koncový vrchol (list)...", teď jsem si to přečetl znovu. Moc se omlouvám za spamování, asi se vrátím na základku a naučím se znovu číst. :)

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson