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
Mějme kompletní graf , kde . Kolik nejménì hran z něj musíme odebrat, aby vznikl nejvýše hranově -souvislý graf? Své tvrzení zdůvodněte!
Moje zdůvodnění se opírá o scripta pana profesora Kováře konkrétně příklad 1.12/1.14 kde //jestli jsem to dobře pochopil je to aspon z části vysvětleno //
Budeme vychazet ze vztahu pro Stupně vrcholù kde každy vrchol grafu je sousední se všemu ostatními vrcholy,a stupen každého vrcholu je .
To využijem i pro náš příklad kde vrcholu musí vytvořit stupen vrcholu.
Jestliže bude n=2,tak = kde stupen každeho vrcholu bude = stupòova posloupnost (3,3,3,3),pro to aby jsme dostali stupen vrcholu je potřeba odebrat právě hran aby vznikl stupen vrcholu stupnova posloupnost (2,2,2,2)
Offline
Ne, zdůvodnění není správně. Zaměňujete pojmy: stupeň vrcholů v grafu a stupeň souvislosti grafu. O stupních souvislosti v první kapitole mého skritpta není psáno a další kapitoly nejsou dopsány. Avšak ve skriptech doc. Hliněného zde na straně 60 najdete definici a několik příkladů, ve cvičení zde najdete na straně 48 několik příkladů. Podrobný komentář byl na přednášce.
Není pravda, že je potřeba odebrat právě n hran.
Offline
Jsem naprosto zoufaly takže zkusím výstřel do tmy.
Jestliže mám souvislý graf tak jeho hrany se určují podle
Takže když mám souvisly graf tak jeho hrany se určují podle
Když zvětšujem n tak se vždy zvýší i stupen vrcholu,a podle mě nemusíme odebrat žádnou hranu,protože
je hranově -souvislý graf
Offline
↑ Koube:Reaguje na předchozí příspěvek. To je opravdu výstřel do tmy. Co to znamená "hrany se určují podle "?
Soustřeďme se na hranovou souvislost kompletního grafu. Jaká je hranová souvislost ? A proč?
Je graf hranově 1-souvislý? A proč?
A je hranově 2-souvislý? hranově 3-souvislý? hranově 4-souvislý?hranově 5-souvislý?hranově 6-souvislý? hranově 7-souvislý? A u každé odpovědi vysvětlete proč.
Offline
Hranová souvislost je .
K další otazce se nebudu vyjadřovat i když věřím že by mi to pomohlo,ale zkusím
je vždy souvislý takže si myslím že když odeberu jednu hranu vznikne hranově souvislý graf
Zkusil jsem se na to podívat ještě jednou pomocí Mengerovy věty,tak doufám že to je pravda
Offline
↑ Koube:
ja suhlasim, aj mne to tak vyslo, skusala som aj tu Mengerovu vetu
ak to tak nie je tak uz neviem ako
Offline