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:k*(32-k)=-k^2+32k=-(k-16)^2+16^2
Ennek az érteke akkor a legnagyobb, amikor k-16 abszolut értéke a legnagyobb. A k-ra megengedett tartományban. A csúcsok száma az első csoportban legalább 1 vagy legfeljebb 31.
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!