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 05. 02. 2013 19:02 — Editoval m.bruna (05. 02. 2013 19:09)
rovinny graf - isomorfismus
Chtel bych se ujistit, ze chapu rovinne grafy spravne. Muzete mi to prosim potvrdit?
1) Vsechny zde uvedene rovinne grafy maji 5 uzlu a 3 steny.
2) Tyto dva rovinne grafy jsou isomorfni. Cela trida isomorfismu tohoto rovinneho grafu ma celkem 4 grafy.
3) Zadna dvojice rovinnych grafu neni isomorfni (a vsechny splnuji bod 1).
4) Kolik neisomorfnich rovinnych grafu lze sestrojit? (5 uzlu, 3 steny) Existuje nejaky efektivni zpusob, jak k tomu dojit?
PS: Kdyby chtel neco nekdo kreslit, neco ukazat ... muzete ZDE.
Bude stacit, kdyz pak kliknete na "Save" a zde vlozite obrazek jako retezec.
Zdejsi grafy (Load, vlozit tento retezec) :
Code:
{"vertices":[{"id":110,"value":"","x":48,"y":154},{"id":111,"value":"","x":48,"y":92},{"id":112,"value":"","x":122,"y":92},{"id":113,"value":"","x":122,"y":154},{"id":118,"value":"","x":86,"y":56},{"id":121,"value":"","x":242,"y":94},{"id":122,"value":"","x":175,"y":155},{"id":123,"value":"","x":175,"y":94},{"id":124,"value":"","x":208,"y":127},{"id":125,"value":"","x":242,"y":155},{"id":132,"value":"","x":297,"y":95},{"id":133,"value":"","x":297,"y":154},{"id":134,"value":"","x":360,"y":95},{"id":135,"value":"","x":360,"y":154},{"id":136,"value":"","x":329,"y":124}],"edges":[{"id":114,"value":"","from":111,"to":112,"directed":false},{"id":115,"value":"","from":111,"to":110,"directed":false},{"id":116,"value":"","from":112,"to":113,"directed":false},{"id":117,"value":"","from":113,"to":110,"directed":false},{"id":119,"value":"","from":118,"to":111,"directed":false},{"id":120,"value":"","from":118,"to":112,"directed":false},{"id":126,"value":"","from":122,"to":125,"directed":false},{"id":127,"value":"","from":123,"to":122,"directed":false},{"id":128,"value":"","from":121,"to":125,"directed":false},{"id":129,"value":"","from":123,"to":121,"directed":false},{"id":130,"value":"","from":124,"to":123,"directed":false},{"id":131,"value":"","from":124,"to":121,"directed":false},{"id":138,"value":"","from":132,"to":134,"directed":false},{"id":139,"value":"","from":133,"to":135,"directed":false},{"id":140,"value":"","from":132,"to":133,"directed":false},{"id":141,"value":"","from":134,"to":135,"directed":false},{"id":142,"value":"","from":133,"to":136,"directed":false},{"id":143,"value":"","from":136,"to":134,"directed":false}],"x":0,"y":0}Offline
#2 09. 02. 2013 23:32
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: rovinny graf - isomorfismus
1) Ano.
2) Jsou isomorfní. Bohužel nevím, co je třída isomorfismů grafu. Počet grafů s daným grafem izomorfních je nekonečný. Pro pevně danou množinu vrcholů existuje 60 grafů izomorfních s tímto "domečkem".
3) První a druhý izomorfní jsou.
4) Graf má dvě stěny, které jsou v nakreslení konečné a třetí je nekonečná. Ty dvě konečné stěny jistě nemohou mít víc než 5 vrcholů, jistě mají alespoň tři vrcholy. Je tedy 6 možností:
* trojúhelník,trojúhelník
* troj, čtyř
* troj, pěti
* čtyř, čtyř
* čtyř, pěti
* pěti, pěti
pro každou lze rozmyslet, kolika způsoby lze tyto stěny "přilepit" k sobě. Pro pětiúhelník-pětiúhelník třeba vyjde 0. Pak je ještě potřeba rozmyslet, jestli jsou některé z nalezených grafů izomorfní.
BRKOS - matematický korespondenční seminář pro střední školy
Offline