Cím: Megjegyzés az F.2218-as feladathoz (függvények gráfja)
Szerző(k):  Kepes János 
Füzet: 1980/március, 109 - 110. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

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 f(f(x))=g(x) alakú, úgynevezett függvényegyenlet megoldhatóságát vizsgáltuk: adott volt a g(x) függvény és kerestünk olyan f(x) 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 függvény értelmezési tartományának minden x pontját egy nyíllal (irányított éllel) összekötjük az értékkészlet megfelelő f(x) pontjával, egy irányított gráfot kapunk. Ezt a gráfot hívjuk az f 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 f minden x-hez egyetlen f(x) értéket rendel, a gráf minden pontjából (csúcsából) pontosan egy nyíl indul ki. Másrészt f 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 f 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 f gráfját már sikerült megszerkesztenünk, abból f(f(x)) 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 f gráfjában egy nyíl x-et f(x)-szel, az ehhez csatlakozó nyíl f(x)-et f(f(x))-szel köti össze, következésképpen az új nyíl x-ből f(f(x))-be vezet. Ha veszünk f gráfjában egy láncot, az f(f(x)) 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 2k hosszú kör két k hosszúságú körre bomlik fel. Ezek szerint f(f(x)) gráfjában páros hosszú kört csak úgy kaphatunk, ha f gráfjában egy kétszer olyan hosszú kör szerepelt, ami viszont ketté bomlik. Így azt kaptuk, hogy f(f(x)) gráfjában minden páros hosszúságú körből páros soknak kell lennie.
Ha tehát a g függvény gráfjában valamilyen k-ra páratlan sok 2k hosszúságú kör van, akkor ez a g biztosan nem állítható elő f(f(x)) alakban. A 2218. feladat megoldása is azon múlt, hogy a g(x)=x2-2 függvény gráfjában egyetlen 2 hosszú kör található.
Az eddigiek alapján szükséges feltételt kaptunk arra, hogy egy g(x) függvény előállítható legyen f(f(x)) alakban: g(x) 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ő g függvényekre elegendő is. A láncokat és a páros hosszúságú köröket párokba osztjuk, f(x)-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, 2k+1 hosszúságú kör egy x pontjában f(x)-et csak g1^(g2^...(gk+1^(x),...))-nek definiálhatjuk, ezzel viszont az egész körre a definíció megfelelő.
Ha g 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 g(x) 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 k hosszú körök pontjai, gyökei a g1^(g2^(...gk^(x)...))=x egyenletnek, egészen pontosan ennek az egyenletnek gyökei azok a pontok, amelyek olyan i hosszúságú körökhöz tartoznak, ahol i osztója k-nak (i=1 is lehetséges). A láncok megkeresésében arra támaszkodhatunk, hogy ha g az x értelmezési tartományának egy részéből vett értékeket ugyanabba a részbe viszi, és itt vagy minden x-re f(x)>x, vagy minden x-re f(x)<x, vagy minden x-re |f(x)|>|x|, vagy minden x-re |f(x)|<|x|, akkor ezek az értékek nem lehetnek körök részei, hiszen például f(x)<x esetén f1^(...fn^(x)...)<x teljesül tetszőleges n-re.
Végül egy általánosítási lehetőség: Előállítható-e a g(x) függvény f1^(f2^(...fn^(x)...)) alakban? A fenti gondolatmenet úgy módosul, hogy f gráfjában egy k hosszúságú körből (k,n) darab k(k,n) hosszúságú kör lesz, egy láncból pedig n új lánc. Ebből további szükséges feltételeket olvashatunk ki, például ha n=pr, ahol p prímszám, akkor g gráfjában p hosszúságú körből vagy végtelen soknak, vagy n-nel osztható darabnak kell lennie stb.

 

Az eddigiek ismeretében oldjuk meg a következő feladatokat:
 

1. Bizonyítsuk be, hogy g(x)=x+2x függvényhez nincs olyan f(x), melyre f(f(x))=g(x).
 

2. Bizonyítsuk be, hogy g(x)=-x3 nem állítható elő f(f(x)) alakban. Könnyen látható, hogy a h(x)=x3-höz van ilyen f. Mi az oka ennek az eltérésnek?