Bizonyitsuk be hogy egy n csucsu összefüggő grafnak legalább n-1 éle van???
Én ezt szovegesen tudom igazolni.
De nem tudom jó e?
Tehát n csucsu a grafunk.
Ekkor A csúcsot kössük össze az összes többi csúccsal, ekkor n-1 élünk lesz.
Ekkor A minden csúccsal össze van kötve, tehát bármely csucsbol eljutunk A csucsba, majd A csucsbol eljutunk bármely más csucsba, azaz összefüggő grafunk lesz.
És ekkor lesz a legkevesebb az èlek száma, hiszen minden csúcs csak egyetlen egy másik csúccsal van összekötve.
De ha n-1-nel kevesebb èlünk lesz, akkor egy csúccsal nem lesz összekötve A csúcs, nevezzük ezt B csúcsnak.
Tehát bármely nem B csucsbol eljutunk A csucsba, de A csucsbol nem fogunk eljutni B csucsba.
Ekkor a graf nem lesz összefüggő.
válasza:
válasza:"hiszen minden csúcs csak egyetlen egy másik csúccsal van összekötve."
Ez A-ra nem teljesül.
Teljes indukcióval egyszerűen bizonyítható az állítás. Egyesével növelve a csúcsok számát.
#1-es
Ha A csúcsot az összes többi csúccsal osszekotjuk, akkor A csúcs össze van kötve B csúccsal, és C csúccsal is.
Tehát B csucsbol eljutunk A csúcson keresztül C csucsba, azaz létezik közöttük út.
#2-es
Ha megkérlek tudnád részletezni a levezetest?
válasza:Teljes indukció:
1. Egy kiindulási helyzetre bizonyítjuk, hogy az állítás igaz.
2. Levezetjük, hogy ha n-1-re igaz, akkor abból bizonyítható, hogy n-re is igaz.
1. Kiinduló helyzet egy két csúcsú gráf.
2. Ha tudjuk hogy bármely n-1 csúcsú összefüggő gráfnak, legalább n-2 éle van, akkor egy csúcsot hozzáadva a keletkező gráf csak akkor lehet összefüggő, ha ..., mert ...
válasza:Az állítás ebben a formában nem igaz.
Úgy lesz igaz, hogy EGYSZERŰ gráfban.
A bizonyítás pedig úgy van, ahogy 4-es írja. Egyébként ez az gráfelmélet egyik legalapabb tétele, így a bizonyítását megtalálod. Az így kapott gráfot egyébként fának hívják, amiről a következőket lejet tudni;
Az n csúcsú fának (n-1) éle van, és ha n>=3, akkor (n-1) darab olyan csúcsa, amelynek fokszáma 1.
Minimálisan összefüggő (tehát éltörlésre szétesik)
Maximálisan körmentes (bármilyen élt behúzva lesz benne (gráfelméleti) kör).
Köszönöm a segitseget nektek.
Így a segítséggel, saját szavaimmal erre a bizonyításra jutottam:
1.
Egy n csúcsu összefüggő egyszerű grafban, n-1 él esetén biztosan van legalább egy elsőfokú csúcs.
Ezt gyorsan Bizonyitsuk is:
Indirekt módon:
Mindegyik csúcshoz tartozzon legalább 2 él.
Ekkor a fokszamosszeguk legalább 2n.
Tehát az elek száma legalább 2n/2.
2n/2<=n-1
n<=n-1
0<=-1
Tehát ellentmondásra jutottunk.
Azaz az 1. Állítás igaz.
2. Egy n csucsu összefüggő egyszerű graf n-1 él esetén az elsőfokú csúcsot és a hozzátartozó élt eltávolítva, n-1 csúcsú grafot kapunk, amelynek az indukciós feltevesunk szerint legalább n-2 éle van, tehát az n csucsu grafnak legalább n-1 éle van.
válasza:Én a teljes indukciós bizonyításként egyszerűen a következőkre gondoltam:
1. Egy kétcsúcsú gráf csak akkor lehet összefüggő, ha van legalább 1 éle.
2. Ha tudjuk hogy bármely n-1 csúcsú összefüggő gráfnak, legalább n-2 éle van, akkor egy csúcsot hozzáadva a keletkező gráf csak akkor lehet összefüggő, ha az új csúcs legalább 1 éllel csatlakozik a régi gráfhoz. Tehát az n csúcsú öszefüggő gráfnak legalább n-1 éle van.
(Csak a formalitás kedvééért: A leírt módszerrel bármely n csúcsú gráf létrehozható, mert minden n csúcsú gráf szétválasztható egy n-1 csúcsúra és egy csúcsra. És a folyamat fordítva is működik.)
válasza: válasza:#8
"A 7-es hozzászólásbeli bizonyítás azért nem helyes, mert egy új csúcs hozzáadásával nem csak összefüggő gráfból kiindulva lehet összefüggő gráfot kapni"
Teljesen igazad van.
válasza:#9
Semmi gond, könnyű benézni az ilyeneket.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!