Grafelmeleti feladat?
Egy országban 32 település van, és 466 db út.
Minden út két települést köt össze, és két települést csak egy út köthet össze.
Igazoljuk hogy bármely településből eljuthatunk bármely telepulesbe!!
Én így igazolnam.
Ha van olyan település ahova nem vezet út, akkor a maximalis utak száma 31*30/2=465.
És tudjuk hogy 466 út van.
Tehát annak a településnek is csatlakoznia kell a grafhoz úttal, amelyet kihagytunk.
Ekkor ugye a 31 település között teljes Graf alakul ki, majd ebbe csatlakoztatjuk a 32.-ik települést, azaz biztosan eljutunk bármely pontból bármely másik pontba.
Van hiba az elmeletemben?
válasza: válasza:A bizonyítás így nézne ki;
A 32 pontú teljes gráfnak (32*31)/2=496 éle van.
Tétel: az n>=2 csúcsú (egyszerű) teljes gráf élösszefüggőségi száma (n-2). Ezt azt jelenti, hogy (n-2) darab élt akárhogyan törölve a gráf mindenképp összefüggő marad, viszont ki lehet törölni (n-2) darab élt úgy, hogy a következő él törlésével szétesik a gráf.
Esetünkben ez azt jelenti, hogy a 496 élű teljes gráfból (32-2)=30 él minden további nélkül törölhető úgy, hogy a gráf összefüggő maradjon, tehát ha a gráfnak 466 éle van, akkor biztosan összefüggő marad.
Ezzel be is tudtuk bizonyítani az állítást.
Nagyon szépen köszönöm a válaszokat.
Amúgy nem is hallottam róla hogy van graf osszefuggesi “szabály”.
Az első válaszomat pontosítom.
Tehát azt már igazoltam hogy nem lehet a grafban izolált csúcs.
És mivel 466 el van a grafban, ezért muszály legyen olyan A csúcs amely 30 másik csúccsal van összekötve.
Mert ha nem lenne akkor a maximalis elek száma 32*29/2=464 el lenne ami keves.
Tulajdonképpen a 466 db élt arra tudjuk felhasználni hogy meg tudjuk határozni hogy kell lenni olyan A csúcsnak amely legalább 30 másik csúcshoz csatlakozik.
Ekkor pontosan egy csúcshoz nem fog csatlakozni A csúcs, nevezzük ezt B csúcsnak.
De tudjuk hogy nincs izolált csucsunk, ezért B csúcs csatlakozni fog olyan csúcshoz amely csatlakozik A csúcshoz, ez alapján A csucsbol eljuthatunk bárhova, még B csucsba is, és ez igaz B csúcsra is.
Ezzel igazoljuk az állítást.
Így már helyes lesz?
válasza:Még ez sem az igazi. Mivel a szorzatra 464 jött ki, ezért ezzel azt igazolnád, hogy 465 él is elég lenne, ami pedig nem igaz, mivel 465 éllel még lehet nem összefüggő a gráf. Ez az eset akkor fennáll, hogyha van egy izolált csúcsunk, a többi csúcs pedig össze van kötve, mindenki mindenkivel, de persze azt igazoltad, hogy 1 darab izolált csúcs nem lehet, de az előfordulhat esetleg máshogyan is, hogy 465 él van, mégsem összefüggő. Neked még azt kellene megmutatnod, hogy csak abban az esetben nem lesz 465 éllel összefüggő a gráf, hogyha van izolált csúcs.
Hol találkoztál ezzel a feladattal? Középiskolában vagy egyetemen? Mert ha egyetemen, akkor az általam felírt tétellel már kellett találkoznod.
válasza:Én soha az életben nem találkoztam az általad felírt tétellel. Nem is hiszem, hogy ez egy létező tétel.
Gyanítom a gráfelméletet tanulók elenyésző hányada (évente ~30 ember) kivételével senki nem találkozott vele.
Amúgy szerintem ez a bizonyítás jó.
Megkaptam a megoldást a feladathoz.
Itt a link.
Ez alapján az én elméletem jó bizonyitasnak tűnik.
Mivel A 30 fokszam esetén a Graf összefüggő.
válasza:Egy másik bizonyítás:
⤒ a gráf nem összefüggő, ekkor szétesik komponensekre. Uniózzuk össze ezeket a komponenseket két darab (nemüres) csúcsosztállyá. A két csúcsosztály között k*(32-k) >= 31 él nem fut, de a gráfból csak 30 él hiányzik ↯
7#-es.
Ezt át kell gondoljam, kicsit nehéznek tűnik.
De akkor az én bizonyításom jó?
válasza:#8
Nem nehéz az, csak más szavakkal kell elmondani.
Ha a gráf nem összefüggő, akkor 2 vagy több kis gráfból áll. Osszuk a kis gráfokat két csoportba. Az egyik csoportban a csúcsok száma legyen összesen k, a másikban 32-k. A két csoport között nincsenek összeköttetések ezért k*(32-k) >= 31 éllel kevesebb van mint a teljes gráf 32*31/2=496 éle lenne. Emiatt, ha a gráf nem volna összefüggő, akkor legfeljebb 496-31=465 éle lehetne.
Ez elég jó bizonyitasnak tűnik.
Lenne ide egy kérdésem.
Honnan tudjuk hogy minimum 31 éllel lesz kevesebb ha a graf nem összefüggő?
Azaz maximum 465 èl lehet ekkor a grafnak?
Tehát honnan tudjuk hogy ez a minimum értek?
Pl.: ha 5 és 27 pontra osztom a grafot az nem kaphat nagyobb él számot mint az 1 és 31 pontu graf?
Tehát k*(32-k)>= itt mi a minimum értek?
Esetleg számtani és mértani kozeppel vizsgálni?
Vagy ez mindig akkor lesz minimum ha k=1?
Minden pont szám esetében?
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!