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ő.
Sziasztok!
Lenne ide egy újabb bizonyítani való állítás.
Állítás:
Ha egy grafban minden csúcs fokszama legalább ketto, akkor a graf tartalmaz kort.
Az én bizonyitasom:
Legyen A1 egyik ismerőse A2.
A2-nek A1-tol különböző ismerőse A3.
A3-nak A2-tol különböző ismerőse A4.
………
An-nek An-1-tol különböző ismerőse An+1.
Lesz ilyen, hiszen mindenkinek legalább ketto ismerőse van.
Előbb utóbb olyan emberhez jutunk, aki már szerepelt a felsorolásban.
Az első ember aki másodszorra szerepel a felsorolasban, jelöljük Ak-val.
Ekkor Ak,Ak+1,….Am,Am+1 felsorolást jelöljük Ax-el, ahol Am+1=Ak.
Ekkor az Ax felsorolást ultessul le egy kor alakú asztalhoz köre, ugyanabban a felsorolasban mint ahogyan az Ax felsorolasban szerepelnek.
Ekkor minden ember mellett két ismerőse fog ülni, és kort fognak alkotni.
Rendben van ez így?
Vagy esetleg egyszerűbben lehet, vagy pontosabban?
Köszönöm szépen.
Viszont van amit nem tudok bizonyítani.
Egy n csucsu fának, n-1 elé van.
Ezt nem sikerül bizonyitanom.
Esetleg egy kis segitseget tudtok adni?
válasza:Szavakkal megfogalmazva így tudom:
Állítás:
Az n csucsu fának, n-1 elé van.
Bizonyítás:
Tudjuk hogy egy fa, összefüggő egyszerű, kormentes grafot jelent.
Mivel egyszerű, összefüggő gráfok van szó tehát, ezért legalább n-1 elé van a grafnak.
És tudjuk hogy a fa, kormentes.
Ahhoz hogy egy összefüggő , egyszerű graf biztosan tartalmazzon kort, minden csúcsához legalabb ketto el tartozik.
De mivel kormentes ezért nen minden csucsahoz tartozik ketto el, azaz az elek száma kisebb mint n.
Ahhoz hogy összefüggő egyszerű grafunk legyen az elek száma minimum n-1 kell legyen, viszont kormentes a grafunk ezért kisebb az elek száma mint n.
Tehát n-1<=elek száma<n.
Ennek az egyenlotlensegnek viszont csak az felel meg ha az elek száma n-1.
Ezzel bizonyítottuk az állítást.
válasza:"Ahhoz hogy egy összefüggő , egyszerű graf biztosan tartalmazzon kort, minden csúcsához legalabb ketto el tartozik."
Erre ellenpélda egy háromszög, amihez egy negyedik csúcs 1 éllel csatlakozik.
válasza:"De mivel kormentes ezért nen minden csucsahoz tartozik ketto el, azaz az elek száma kisebb mint n."
De egy csúcshoz nagyon sok él is tartozhat. Pl. ha egy csúcshoz van kötve az összes többi. Ezért nem elég abból kiindulni, hogy van olyan csúcs amihez kevesebb, mint 2 él tartozik.
Ezt kicsit pontositom.
16#-os.
Azt írtam hogy ahhoz hogy egy graf BIZTOSAN tartalmazzon kort, ahhoz kell hogy legalább minden csúcsahoz 2 el csatlakozzon.
Más esetben is tartalmazhat kort, de nem biztosan.
4 pontu grafnal például az A csúcs össze van kötve a többi 3 csúccsal.
Ekkor összefüggő, egyszerű, és nem tartalmaz kort, viszont van 2nel nagyobb fokszamu pontja.
Tehát hogy BIZTOSAN tartalmazzon kort egy összefüggő egyszerű graf, ahhoz minden csúcsát legalább 2 éllel kell összekötni.
Elnézést ha pontatlanul írtam le az előző valaszaimban.
Térjünk vissza ehhez:
Állítás: egy n csucsu fának n-1 elé van.
Bizonyítás:
A fa összefüggő, egyszerű, és kormentes graf.
Ahhoz hogy összefüggő legyen legalább n-1 ele kell legyen a grafnak.
Mivel kormentes ezért van benne biztosan elsőfokú csúcs.
n=3 esetén hogy összefüggő, egyszerű, kormentes grafunk legyen, ahhoz 2 élt tartalmazhat a graf.
Ahhoz hogy ezt az összefüggő egyszerű kormentes grafot mindig tartani tudjuk ahhoz plusz egy csúcs hozzáadásával mindig csak legfeljebb 1 élt adhatunk a grafunkhoz.
Hiszen ha n>3 esetén plusz egy élt adunk a meglévő grafhoz, akkor maximum csak egy élt húzhatunk ebből a hozzáadott csucsbol, ellenkező esetben 2 vafy annál több csúccsal lesz összekötve, ami azt jelenti hogy haromszoget biztosan alkotni fog így ez a csúcs, és azok a csúcsok amikhez kötjük.
Teljes indukcioval bizonyitsuk az állítást.
Tehát n=3 esetén igaz hogy maximum n-1 élünk lehet.
A fentiek alapján n+1 csucsu graf esetén maximum n csucsunk lehet, és az össze függőség miatt minimum n.
Ez alapján n csucsu graf esetén n-1 él esetén fog minden igénynek megfelelni a grafunk.
válasza:"Ahhoz hogy ezt az összefüggő egyszerű kormentes grafot mindig tartani tudjuk ahhoz plusz egy csúcs hozzáadásával mindig csak legfeljebb 1 élt adhatunk a grafunkhoz."
Ebben -szerintem- ugyanaz a hiba, mint amit én a 7-es bizonyításban elkövettem és amire 8-as rámutatott. Nem biztos, hogy az n csúcsú fához csak n-1 csúcsú fától lehet eljutni. Lehet egy n-1 csúcsú nem összefüggő gráftől is.
Szerintem a teljes indukcióban fordítva kellene haladni. Bizonyítottad, hogy ha egy egyszerű, összefüggő gráfban minden csúcs legalább másodfokú, akkor van benne kör. Ezért egy fában mindig van elsőfokú csúcs.
Ha ezt a fáról levágjuk, attől továbra is fa marad és az élek száma pontosan eggyel csökken. És így n-3 lépésben eljutunk a 3 csúcsú fához, aminek pontosan két éle van.
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, 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!