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 01. 12. 2007 17:36
Strnulý graf
Vysokoškolská matematika vyvrátila moji představu o tom, co je to graf. Jistě víte, co mám na mysli - teorii grafů. Je tu ale něco, s čím si nevím rady. Pojem strnulý graf - tedy graf, který má pouze jeden automorfismus (zobrazení sama na sebe). Potřeboval bych nějaký příklad takového grafu, dáte mi jej?
Zároveň by mě zajímal tenhle příklad: pro jaká N existuje graf na n vrcholech, který má všechny stupně až na dva různé.
Díky za pomoc!
Offline
#2 02. 12. 2007 14:20
Re: Strnulý graf
http://mathworld.wolfram.com/IdentityGraph.html - tomu strnulemu grafu se take rika asymetrický
Lasciate ogni speranza. | Podílí se na Encyklopedii Fyziky (http://fyzika.jreichl.com) | Oblíbený IT projekt http://online-domain-tools.com
Offline
#4 03. 12. 2007 20:28
Re: Strnulý graf
http://matematika.havrlant.net/forum/vi … p?pid=2271 - ja to už také řešil....
ten graf, který navrhuješ ty podle mě strnulý není a to proto, že se hned nabízí bijekce, která mi přejmenuje vrchol jedna na vrchol dva a je to pořád stejný graf..
Lasciate ogni speranza. | Podílí se na Encyklopedii Fyziky (http://fyzika.jreichl.com) | Oblíbený IT projekt http://online-domain-tools.com
Offline
#5 03. 12. 2007 20:29
- jelena
- Jelena
- Místo: Opava
- Příspěvky: 30020
- Škola: MITHT (abs. 1986)
- Pozice: plním požadavky ostatních
- Reputace: 100
Re: Strnulý graf
Troufla jsem se zeptat u odborniku, zda anglicky nazev tohoto grafu neni neco jako "Rigid graph" a bylo mi receno, ze jo.
Cimz to postupuji dal, ale ze bych tomu rozumela vice, to zas ne.
Zkus kouknout timto smerem, treba pomuze :-)
http://mathworld.wolfram.com/RigidGraph.html
http://kam.mff.cuni.cz/~kamserie/serie/ … 7/s812.pdf
Offline
#6 04. 12. 2007 09:49
Re: Strnulý graf
Co byste jeste pratele chteli vice? Na te adrese, kterou sem poslal Saturday je prikladu vice nez dost. Pokud nekdo doufa, ze objevi strnuly graf na mene nez sesti a vice nez jednom vrcholu, necht prosim rychle doufat prestane, nebot takovych neni.
Nothing in the world that's worth having comes easy.
Always do what you are most afraid of.
Offline
#8 05. 12. 2007 00:20
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Strnulý graf
Tož pro n=2 takový graf vidíme (o--o), pro n=3 taky (o--o--o), pro n=4 taky...
čímž máme pěkný základ pro indukci. A jak na ten indukční krok? Uvažme graf o n vrcholech takový, že stupně jeho vrcholů jsou 1,2,...,k-1,k,k,k+1,...,n-1 (takový z indukčního předpokladu máme). A teď k němu přidáme vrchol, který spojíme se všemi vrcholy stupně >k a s jedním z vrcholů stupně k. Stupně původních vrcholů tak vytvoří posloupnost od 1 do n, stupeň přidaného vrcholu bude nějaké t. Takže kromě t není žádný stupeň zastoupen dvakrát.
QED :)
BRKOS - matematický korespondenční seminář pro střední školy
Offline