A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. A feladatban egy alakú, úgynevezett függvényegyenlet megoldhatóságát vizsgáltuk: adott volt a függvény és kerestünk olyan függvényt, amelyre a megadott egyenlőség teljesül. Az ehhez hasonló feladatok megoldásában, illetve a megoldhatóság feltételeinek vizsgálatában hasznos segédeszköz a függvény gráfjának fogalma. Ha az függvény értelmezési tartományának minden pontját egy nyíllal (irányított éllel) összekötjük az értékkészlet megfelelő pontjával, egy irányított gráfot kapunk. Ezt a gráfot hívjuk az függvény gráfjának. A gráfnak egy része összefüggő, ha bármely pontjából bármely pontjába az élek mentén (de nem feltétlenül a nyilak irányában) el lehet jutni. A gráf összefüggő részei a gráf komponensei. Vizsgáljuk most meg az olyan kölcsönösen egyértelmű függvény komponenseit, melyeknek értékkészlete és értelmezési tartománya is egybeesik. (Később látni fogjuk, hogy valójában az ilyen függvények fontosak számunkra.) Miután minden -hez egyetlen értéket rendel, a gráf minden pontjából (csúcsából) pontosan egy nyíl indul ki. Másrészt egy-egy értelmű, azért minden pontba pontosan egy nyíl érkezik. Egy pontból kiindulva kövessük a nyilak útját! Ha valamelyik nyíl ugyanebbe a pontba visszavezet, akkor a megfelelő komponens kör, míg ha minden nyíl addig nem szereplő új pontba vezet, akkor a komponens két irányban végtelen lánc. Olyan függvényeknél, ahol az értelmezési tartomány és értékkészlet nem azonos, a gráfban lehetnek kezdő- és végpontok is (azaz olyan pontok, melyekbe nem érkezik, illetve amelyekből nem indul egyetlen nyíl sem). Ezenkívül ha nem kölcsönösen egyértelmű, akkor egy lánc vagy kör pontjaiba külső pontokból is érkezhetnek nyilak (viszont nem indulhatnak ki külső pontok felé, ezért például egyetlen komponens sem tartalmazhat egynél több kört). Ha gráfját már sikerült megszerkesztenünk, abból gráfját könnyen megkaphatjuk a következő módon. Az eredeti gráf két, egymáshoz csatlakozó nyílból álló irányított útját egyetlen nyíllal helyettesítjük, hiszen gráfjában egy nyíl -et -szel, az ehhez csatlakozó nyíl -et -szel köti össze, következésképpen az új nyíl -ből -be vezet. Ha veszünk gráfjában egy láncot, az gráfjában két láncra bomlik, továbbá könnyű ellenőrizni, hogy páratlan hosszúságú körnek ugyanolyan hosszú kör felel meg, viszont egy hosszú kör két hosszúságú körre bomlik fel. Ezek szerint gráfjában páros hosszú kört csak úgy kaphatunk, ha gráfjában egy kétszer olyan hosszú kör szerepelt, ami viszont ketté bomlik. Így azt kaptuk, hogy gráfjában minden páros hosszúságú körből páros soknak kell lennie. Ha tehát a függvény gráfjában valamilyen -ra páratlan sok hosszúságú kör van, akkor ez a biztosan nem állítható elő alakban. A 2218. feladat megoldása is azon múlt, hogy a függvény gráfjában egyetlen hosszú kör található. Az eddigiek alapján szükséges feltételt kaptunk arra, hogy egy függvény előállítható legyen alakban: gráfjában minden végtelen láncból és minden páros hosszúságú körből vagy páros soknak, vagy végtelen soknak kell lennie. Ez a feltétel kölcsönösen egyértelmű és azonos értelmezési tartománnyal és értékkészlettel rendelkező függvényekre elegendő is. A láncokat és a páros hosszúságú köröket párokba osztjuk, -et értelmezzük az egyik lánc (kör) egyik elemén úgy, hogy ott a másik láncon (körön) levő tetszőleges értéket vegyen föl, ezt kiterjeszthetjük a lánc (kör) egészére. A páratlan, hosszúságú kör egy pontjában -et csak -nek definiálhatjuk, ezzel viszont az egész körre a definíció megfelelő. Ha nem teljesíti a fenti megszorításokat, akkor is hasonló jellegű, csak körülményesebb feltételek szabhatók. Felmerül a kérdés: tetszőleges függvénynek hogyan határozhatjuk meg a gráfját. Ez általában nem könnyű, és nem is mindig megoldható feladat, de a következő néhány gondolat sok esetben segíthet. A hosszú körök pontjai, gyökei a egyenletnek, egészen pontosan ennek az egyenletnek gyökei azok a pontok, amelyek olyan hosszúságú körökhöz tartoznak, ahol osztója -nak ( is lehetséges). A láncok megkeresésében arra támaszkodhatunk, hogy ha az értelmezési tartományának egy részéből vett értékeket ugyanabba a részbe viszi, és itt vagy minden -re , vagy minden -re , vagy minden -re , vagy minden -re , akkor ezek az értékek nem lehetnek körök részei, hiszen például esetén teljesül tetszőleges -re. Végül egy általánosítási lehetőség: Előállítható-e a függvény alakban? A fenti gondolatmenet úgy módosul, hogy gráfjában egy hosszúságú körből darab hosszúságú kör lesz, egy láncból pedig új lánc. Ebből további szükséges feltételeket olvashatunk ki, például ha , ahol prímszám, akkor gráfjában hosszúságú körből vagy végtelen soknak, vagy -nel osztható darabnak kell lennie stb. Az eddigiek ismeretében oldjuk meg a következő feladatokat:
1. Bizonyítsuk be, hogy függvényhez nincs olyan , melyre .
2. Bizonyítsuk be, hogy nem állítható elő alakban. Könnyen látható, hogy a -höz van ilyen . Mi az oka ennek az eltérésnek? |