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 16. 01. 2010 22:54
Grafy
Zdravím...
Mohl by mě někdo polopasticky vysvětlit, jak by se dalo řešit toto zadání?
Jaký je minimální a maximální počet hran grafu s n vrcholy a k
komponentami souvislosti?
Teoreticky vím co je to souvislost a co je to komponenta, ale jen velmi základní definici...více o tom - např. příklady atd., se mi nepodařilo zatím na internetu nalézt.
Předem děkuji za jakoukoli pomoc při řešení.
Offline
- (téma jako vyřešené označil(a) Kondr)
#2 16. 01. 2010 23:10
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Grafy
Nejméně hran bude mít, když budou mít jednotlivé komponenty co nejméně hran, tedy když to budou stromy. Nejvíce hran bude mít, když budou komponenty úplné grafy. Kolik hran má k stromů, které mají dohromady n vrcholů? Kolik hran má k-tice úplných grafů, z nichž první je na a_1 vrcholech, druhý na a_2, ..., poslední na a_k?
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#4 22. 01. 2010 22:12
Re: Grafy
Děkuji za příspěvky...
Bohužel jsem to moc nepochopil...
Když jsem to zkoušel zjistit "intuitivně", vyšlo mi, že minimální počet hran grafu s n vrcholy a k komponentamy souvislosti je 0...u maxima tápu, protože když budu mít graf s 8 vrcholy a 3 komponentama, vyjde mi, že maximálně může mít 15 hran, ovšem s n-k+1=6...
Nebo jsem to všechno jen špatně pochopil?
Offline
#5 22. 01. 2010 22:31
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Grafy
Když máš třeba 10 vrcholů a 2 komponenty, tak to bez hran nepůjde. Když vyjdeme z grafu, který má n samostatných vrcholů, tak na snížení počtu komponent o 1 vždy potřebujeme alespoň jednu hranu. Celkem potřebujeme alespoň n-k hran, způsobů jak toho docílit je mnoho (na počet způsobů se naštěstí nikdo neptá).
S maximem má Jonas pravdu, zkus si jeho příspěvek přečíst pozorněji -- nemluví o počtu hran, ale o počtech vrcholů v komponentách. Je potřeba vědět, kolik hran má úplný graf na n-k+1 vrcholech.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#6 23. 01. 2010 10:50
Re: Grafy
↑ Kondr:↑ Kein:
Možná ještě názornější je obrácený postup. Když máme kostru grafu o n vrcholech, tak má n-1 hran. A pro kostru platí, že za každou odebranou hranu, nám počet komponent vzroste o 1. No a protože na začátku je 1 komponenta, a potřebujem jich k, tak musíme odebrat k-1 hran.
Výsledek je samozřejmě stejný.
Dva jsou tisíckrát jeden.
Offline
#7 26. 01. 2010 17:09 — Editoval Kein (26. 01. 2010 17:11)
Re: Grafy
Tak ještě jednou děkuji za pomoc...
Už jsem to konečně pochopil... :) (teda doufám)
Předtím jsem nebral v potaz to, že pokud mám např. úplný graf o 4 vrcholech (6 hran), odebráním hran mi vzniknou 2 2-vrcholové komponenty, každá s jednou hranou...
teď už mě to dává smysl...
Offline