Matematické Fórum

Kein · 28. 01. 2010 19:28

Zdravím,
měl bych tři příklady na grafy s kterými bych potřeboval krapet poradit...

1. Ukažte, že pro libovolný graf $G=(V,E)$ existuje funkce $f: V \rightarrow \mathbb{N}$ taková, že platí $\{u,v\} \in E \Leftrightarrow NSD (f(u), f(v)) > 1$

2. Pro $i \in \mathbb{N}$ označme $p_{i}$ počet vrcholů stupně $i$ ve stromu T. Dokažte, že má-li T alespoň dva vrcholy, platí $p_{1}-p_{3}-2p_{4}-3p_{5}-\dots=2$

3. Dokažte, že v každém souvislém grafu G s alespoň třemi vrcholy existují dva různé vrcholy $u,v \in V(G)$ takové, že všechny grafy G-u, G-v, G\{u,v} jsou souvislé

V případě 1. příkladu si nevím vůbec rady - co je NSD?

V případě 2. příkladu to spíš nechápu

V případě 3. příkladu mě napadlo, že pokud budu mít jakýkoli souvislý graf o velikosti minimálně 3 vrcholů, tak pokud odeberu 2 vrcholy spojené nějakou hranou e, tak mi vznikne cesta nulové délky, což by se dalo brát jako souvislý graf...
V případě, že graf bude obsahovat vrcholů více, tak v případě, úplného grafu a kružnice bude souvislý, ať odeberu vrcholy s tou hranou odkudkoli...
V případě cesty by to platilo jen v případě, že bych odebral vrcholy s hranou jen na začátku, nebo na konci cesty, jinak bude nesouvislý a u bipartitního grafu $K{n,m}$ by n muselo být větší než 2, jinak by opět byl nesouvislý...

Nebo jsem úplně mimo?

petrkovar · 28. 01. 2010 21:59

↑ Kein:1) NSD je největší společný dělitel. Zní zadání opravdu takto? Není řečeno, že zobrazení je injektivní? (Pokud ne, je otázka současně nápovědou)
2) Zkus si to rozepsat aa dosadit pro jeden, dva malé stromy do deseti vrcholů.
3) Tvrzení se má ukázat pro všechny souvislé grafy. Rozebírat speciální případy může něco napovědět, ale rozhodně nemůžeme čekat, že podobně probereme všechny možnosti a budeme hotovi různých tříd grafů je nekonečně mnoho.

Kein · 28. 01. 2010 22:14

↑ petrkovar: Děkuji za odpověď...
add 1) Ano zadání zní takto... u NSD jsem tušl, že to bude mít něco společného s dělitelem, ale nějak jsem nevěděl, jestli to je největší, nebo nejmenší...

Ještě jednou na ty příklady juknu...snad mě něco napadne...

petrkovar · 28. 01. 2010 22:32

↑ Kein:Ooops. Špatně jsem si přečetl zadání prvního příkladu. Takže opravuji nápovědu - už se to řešilo zde

Kein · 29. 01. 2010 00:56 — Editoval Kein (29. 01. 2010 00:57)

add 2) podíval jsem se na tento příklad ještě jednou a zjistil jsem, že pokud odečtu počet všech koncových vrcholů a počtu všech 3-stupňových vrcholů a atd., výsledek mi výjde 2. Počet 2-stupňových vrcholů se nebere v potaz zřejmě kvůli tomu, že nevytvářejí žádné další větve. Dále jsem zjistil, že pokud vynásobim počet vrcholů stromu dvěma a od toho odečtu součet stupnů všech vrcholů grafu, výjde opět dvě...

Ale nemám ponětí, jak bych to měl dokázat...

Kein · 31. 01. 2010 19:51

První příklad už mám, pomohl by mi někdo s příkladem 2 a 3...

Stačilo by trochu "nakopnout"...

Kondr · 31. 01. 2010 20:26

Ke druhému: každý strom má alespoň jeden list. Jeden z listů zvolme a označme za kořen. Každou hranu lze orientovat tak, aby šla směrem od kořene. Pro vrchol v označíme d(v) počet hran, které do něj vstupují snížený o počet hran, které z něj vystupují. Když sečteme d(v) přes všechny vrcholy, musí vyjít 0. Je jasné proč? Je vidět, jak tento součet vyjádřit přes $p_i$ ?

Ke trojce: pokud to platí pro všechny rovinné grafy, platíto pro všechny grafy. Pro ty rovinné se to dá ukázat, když najdeme řez, který ho dělí na dva souvislé grafy a protíná přitom alespoň dvě hrany (aspoň doufám). Je potřeba ošetřit případy, kdy takový řez neexistuje.

Kein · 01. 02. 2010 21:12

↑ Kondr: add 2) je mi jasné proč by mělo vyjít 0, i jak to ověřit v praxi ale teoreticky se mi to nedaří dokázat...

add 3) zde nevím jestli jsem dobře pochopil zadání...tedy zda G-u, G-v, G\{u,v} značí dva vrcholy spojené hranou, nebo jde o libovolné vrcholy a libovolnou hranu...

Kondr · 01. 02. 2010 21:36

↑ Kein: Ke dvojce: nerozumím tomu "je jasné" a "nedaří dokázat". Pokud je jasné proč, pak by neměl být problém to přetavit do důkazu.

Ke trojce: já jsem to bral tak, že G\{u,v} je graf G zbavený vrcholů u i v.

Kein · 01. 02. 2010 21:52

add 2) nj, ale v tom vzorci se to rovna 2...proto ten zádrhel...jediné co mě napadlo a co funguje na všechny stromy je $2 \cdot \mid V \mid - \sum_{v \in V(T)} deg_T(v)$ ...

add 3) zde mě napadlo jen to, že aby to fungovalo, musí oba vrcholy u i v buď ležet na kružnici a mít stupeň max 2, nebo aby nybyli artikulací...

Kondr · 01. 02. 2010 22:32

↑ Kein: ad 2) trik je v tom, že jeden z listů je kořen. Proto $p_1-1$ listů má d(v) rovno 1, jeden list -1. Při sčítání přes všechny uzly máme $(p_1-2)-p_3-2p_4-3p_5-\cdots=0$ .

Kein · 02. 02. 2010 18:44

už jsem to pochopil, děkuju :)

Matematické Fórum

#1 28. 01. 2010 19:28

Grafy II

#2 28. 01. 2010 21:59

Re: Grafy II

#3 28. 01. 2010 22:14

Re: Grafy II

#4 28. 01. 2010 22:32

Re: Grafy II

#5 29. 01. 2010 00:56 — Editoval Kein (29. 01. 2010 00:57)

Re: Grafy II

#6 31. 01. 2010 19:51

Re: Grafy II

#7 31. 01. 2010 20:26

Re: Grafy II

#8 01. 02. 2010 21:12

Re: Grafy II

#9 01. 02. 2010 21:36

Re: Grafy II

#10 01. 02. 2010 21:52

Re: Grafy II

#11 01. 02. 2010 22:32

Re: Grafy II

#12 02. 02. 2010 18:44

Re: Grafy II

Zápatí