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. 06. 2013 17:57
úplné párování nekonečného grafu
Mám graf G = (A ∪ B, E), kde A = {0, 1, 2, . . . }, B = {1, 2, . . . } a hrany jsou E = { { k , k } | k ≥ 1 } ∪ { { 0 , k } | k ≥ 1 } . Proč tento graf nemá úplné párování? v takovémto grafu jsou podle mě spojeny všechny body z A s dohromady všemi vrcholy z B. Tudíž by jej podle mě měl mít ne?
Offline
#2 01. 06. 2013 20:02
- check_drummer
- Příspěvky: 4900
- Reputace: 105
Re: úplné párování nekonečného grafu
↑ Mythic:
Ahoj, nejsou spojeny všechyn se všemi - hrana je jen (k,k) (pro stejné k). Možná by bylo dobré zodpovědět, zda jsou A a B disjunktní nebo ne. Mně z toho zápisu připadá, že ne - pak by ale hrany E tvořily smyčky, a ty jsou mám pocit u klasické definice grafu zakázány.
Budeme předpokládat, že jsou A,B disjunktní. Pokud je to tak - pak 0 je součástí nějaké hrany h1:=(0,k0) nějakého párování a pak tedy neexistuje žádné x takové, že (k0,x) je hranou v tomto párování (jediná možnost je (k0,k0), ale k0 z B už je obsazeno hranou h).
"Máte úhel beta." "No to nemám."
Offline
#3 01. 06. 2013 20:31
Re: úplné párování nekonečného grafu
Teď sem moc nerozuměl. Ale možná mám mezeru v pojmech. Myslel sem, že úplné párování je takové, že každý vrchol z A je v nějakém páru s vrcholem z B a naopak. Jinak řečeno, žádný vrchol nezůstane samotný. Ale ty říkáš, že každý vrchol musí být propojený se všemi ostatními?
Jinak to párování mi tu vycházelo takhle nějak:
http://d.pr/i/w1fv
Offline
#5 01. 06. 2013 21:08
- check_drummer
- Příspěvky: 4900
- Reputace: 105
Re: úplné párování nekonečného grafu
↑ Mythic:
To, že v grafu existují hrany (k,k) (pro všechna k) ale neznamená, že jsou všechny vrcholy spojené se všemi...
"Máte úhel beta." "No to nemám."
Offline