[755] marcius8 | 2014-01-07 10:14:14 |
Köszönöm a hozzászólást. Igazából csak addig jutottam én is, hogy hogyan nézhet ki egy ilyen gráf, és arra jutottam, hogy egy ilyen gráf diszjunkt körökből áll. Tisztelettel: Bertalan Zoltán.
|
Előzmény: [753] aaaa, 2013-12-23 01:12:02 |
|
[754] aaaa | 2013-12-23 02:19:16 |
Némi elírás, a megadott képlet minden gráfra számol, és l-et 3-től kell indítani.
Javítás páros gráfra
Párosra csak a páros tagokat kell összegezni, ezeket is csak 2-től kezdve, így a következőképpen módosulnak a dolgaink:
És G(x)-ben xn együtthatója adja meg a sorrendek számát n!-al osztva.
|
Előzmény: [753] aaaa, 2013-12-23 01:12:02 |
|
[753] aaaa | 2013-12-23 01:12:02 |
Egy előzőhöz hasonló gondolatmenettel valahogy így kellene:
Most irányított gráfra csináljuk: Ha meg meg vannak különböztetve a csúcsok, akkor ugye ezeknek n! sorrendje van. Ezt ugye daraboljuk egy partíció szerint. Mit számolunk többször? Hát, ha ugyanazok a csúcsok más sorrendben, de ugyanabban a ciklikus permutációnak megfelelő sorrendben vannak, illetve ha ugynakkora méretű halmazaink vannak, csak más sorrendben. Most generátorfüggvényt csinálunk, -ra:
Először csak azt vesszük bele a játékba, hogy k darab ugyanakkora halmazt (k-1)! alkalommal számoltunk, vagyis a hatványsora valahogy így nézzen ki egy tényező:
Viszont ezeknek lk darab egymástól független, ugyanolyan gráfot eredményező sorrendje van, tehát:
A keresett generátorfüggvény tehát úgy áll elő, hogy a
Szorzat xn-hez tartozó együtthatóját szorozzuk n!-al, és elvileg készen kellene lennünk. Ha meg irányításfüggetlen, akkor ennek pontosan a fele jó sorrend, ekkor
|
Előzmény: [752] aaaa, 2013-12-23 00:24:11 |
|
[752] aaaa | 2013-12-23 00:24:11 |
Kb. 2 percet gondolkozva rajta a következőre jutottam: Mivel a gráf páros, minden kör 2k hosszú, ahol k2, és ez elég is a párossághoz. Címkézetlen csúcsokon vagyunk, így lényegében n pont partíciónak a száma a kérdés, ahol minden egyes részhalmaz legalább 2 elemet tartalmaz. Ennek a generátorfüggvénye meg:
Aminek a hatványsorának xi-hez tartozó együtthatója épp a 2i-re a nem izomorf fák számát. Ennek első néhány tagja:
g(x)1+x2+x3+2x4+2x5+4x6+4x7+7x8+8x9+12x10+14x11+21x12+24x13+34x14+41x15+55x16+66x17+88x18+105x19+137x20+O[x]21
Itt megtalálod a sorozat néhány következő tagját. Szerintem ez megadja az izomorfia erejéig a jó gráfok számát, csak ki kell fejteni. Azt nem hinném, hogy ennél sokkal explicitebb képlet létezik, mivel azt írja, hogy P(n+1)-P(n) sorozat ez lesz, ahol P(n) a partíciók száma. Kicsit fáradt vagyok már, szóval lehet, hogy valamit elnéztem.
|
Előzmény: [750] marcius8, 2013-12-20 10:04:05 |
|
[751] csábos | 2013-12-22 23:35:36 |
Nem értem a kérdést. Adott a páros gráf? Akkor mik az élei? Ha nem adott, akkor adott két db n-elemű halmaz, és ezen hány olyan páros gráf van, amely diszjunkt körök uniója? Ha a gráf adott, meg kell-e őrizni a paritását?
|
Előzmény: [750] marcius8, 2013-12-20 10:04:05 |
|
[750] marcius8 | 2013-12-20 10:04:05 |
Tekintsünk egy páros gráfot, melynek "2n" csúcsa van. Hányféleképpen lehet ebbe a páros gráfba berajzolni az éleket, úgy hogy minden csúcs foka 2 legyen? Kicsit nehezebb kérdés: ezen lehetőségek között mennyi egymással nem izomorf gráf van? Ha valakinek van ötlete ezzel kapcsolatban, kérem írja le. Előre is köszönettel: Bertalan Zoltán.
|
|
[749] marcius8 | 2013-12-20 10:00:36 |
Tudjuk, hogy ha egy tórusz középkörének sugara "R", meridiánkörének sugara "r", ahol "r" kisebb "R" egyenlőtlenség teljesül (klasszikus úszógumi), akkor a tórusz felszíne 4*pi*pi*R*r és a tórusz térfogata 2*pi*pi*R*r*r. Azt is tudjuk, hogy a pozitív egész számok négyzetének reciprokösszege pi*pi/6. Vajon ez utóbbi állítást nem lehetséges bebizonyítani a tórusz felszínképletének vagy térfogatképletének felhasználásával, tekintettel arra, hogy a "pi*pi" mennyiség itt is és ott is megjelenik? Ha valakinek van ötlete, és megírja, nagyon megköszönöm. Tisztelettel: Bertalan Zoltán.
|
|
|
|
|
[745] Cogito | 2013-12-09 00:40:38 |
Egyetértek, a "2. megoldásbeli" azonosság önmagában tényleg bosszantóan kevés.
Az interneten itt olvashatjuk a The Interesting Around Technical Analysis Three Variable Inequalities - Nguyen Duy Tung, Zhou Yuan Zhe.pdf-et, melynek 10-11. oldalán közlik a feladat egy - még mindig nem teljes és sajnos (sajtó)hibás - megoldását. E hibás helyeket negatívba fordítottam. Ide írom a javításukat:
A fekete hátterű részeknél: az egyenlőtlenség helyesen abc, a 2-esek helyére pedig 1-esek írandók.
Kiegészítésül egy azonosság, amit itt érdemes ismerni: a3b + b3c + c3a - (ab3 + bc3 + ca3) = (a + b + c)(a - c)(c - b)(b - a).
|
|
Előzmény: [741] w, 2013-12-02 20:58:17 |
|
|
|
|
[741] w | 2013-12-02 20:58:17 |
Igen, ez így van, de azzal egyetérthetsz, hogy a "2. megoldásbeli" azonosságot egymagában kicsit szemetebb dolog odavágni. :-) A két megoldás azonban olyan szempontból különbözik egymástól, hogy teljesen eltérő módon lehet rájönni - az 1. megoldás kitalálhatóbb, ha az említett egyenlőtlenségből indulunk ki, a második pedig az egyenlőség-esetből vezeti le a kívánt állítást (ami egyébként önmagában nehéz feladat). A megoldás kialakulásáról ebben a beszélgetésben olvashatunk.
|
Előzmény: [740] Cogito, 2013-12-02 20:10:08 |
|
[740] Cogito | 2013-12-02 20:10:08 |
Nézzük, hogyan jutunk 1-ről a 2-re:
Az "1. megoldás"-ban szereplő triviális egyenlőtlenséggel ekvivalens:
ahová x, y, z értékeit behelyettesítve:
adódik, ahol a bal oldalon álló kifejezés éppen A. Az első "megoldás" tehát ekvivalens a másodikkal! Ezért - valójában - egyetlen "megoldást" mutattál be. Azért használom az idézőjeleket, mert hiányérzetem van. Nem mutattad meg, hogy milyen út, milyen meggondolások vezettek az x-re, y-ra és z-re adott helyettesítésekhez.
|
Előzmény: [739] w, 2013-11-29 22:31:58 |
|
[739] w | 2013-11-29 22:31:58 |
Állítás: .
1. megoldás. Hasonlítsuk össze egy triviális egyenlőtlenséggel, azaz hogy (x+y+z)23(xy+yz+zx) tetszőleges valós x,y,z-re. Ebbe x=a2+bc-ab, y=b2+ca-bc, z=c2+ab-ca értékeket helyettesítve pedig éppen a bizonyítandó adódik!
2. megoldás. Vegyük észre, hogy
Mit szóltok?
|
Előzmény: [733] w, 2013-10-25 23:07:23 |
|
|
[737] HoA | 2013-11-18 15:26:19 |
A követelmény úgy is megfogalmazható, hogy minden kiválasztott négyzetnek páros, minden nem kiválasztott négyzetnek páratlan számú kiválasztott szomszédja legyen.
|
Előzmény: [734] kurthyg, 2013-11-17 00:44:52 |
|
[736] kurthyg | 2013-11-17 11:04:40 |
A kiválasztandó négyzetek sorozata. Számozzuk be a négyzeteket: a bal fölső sarok az 1-es a jobb alsó nxn: tehát balról jobbra és föntről lefelé növekszenek a számok.
Ekkor az út (ha eredetileg minden négyzet fehér volt): 1 3 5 7 9
Ezeket sorban kiválasztva minden négyzet fekete lesz.
|
Előzmény: [735] Sinobi, 2013-11-17 10:48:31 |
|
|
[734] kurthyg | 2013-11-17 00:44:52 |
A következő feladatot szeretném megosztani (persze, lehet, hogy már volt, kb 15 éve olvastam KöMaL-t utoljára, még gimnáziumban).
Adott egy nxn-es négyzetrács csupa fehér négyzettel. Válasszuk ki valamelyik négyzetet, ekkor a kiválasztott négyzet, a tőle jobbra és balra, alatta és fölötte lévők feketévé változnak. És minden egyes későbbi kiválasztás ellentétes színűre változtatja a kiválasztott négyzetet és a szomszédait.
Feladat olyan utat találni, amelynek végén az összes négyzet fekete lesz. Hogyan adható meg általános megoldás?
(Pl.: 1x1-es nél triviális. 2x2-esnél minden négyzetet ki kell választani. 3x3-asnál a sarkokat és a középső négyzetet.)
A probléma általánosítása: az nxn-es négyzetrács néhány négyzete fehér, néhány négyzete fekete. Milyen út vezet csupa fekete négyzethez? Hogyan kereshető meg a megoldás? Van-e mindig megoldás?
|
|
[733] w | 2013-10-25 23:07:23 |
A következő egy rendkívül érdekes, a pozitív valós számokra bizonyítandó egyenlőtlenség (négyzetreemelve a valósokra is érvényes marad!). Annál inkább érdekes, hogy milyen egyszerű alakú, negyedfokú egyenlőtlenség.
Különösen szokatlan az egyenlőség-esete, amit mindenképpen érdemes előre megfigyelni.
(A feladat egyébként valamennyire ismert, egy idő múlva majd elárulom, hol találtam.)
|
|
|
[731] Sinobi | 2013-10-20 01:36:18 |
Bocsánat, nem ilyen alakra kell a végén hozni. Ezt még tovább kell alakítanod, hogy l:=-14/9*m, s akkor azt kapod, hogy:
Amiben még mindig ott van n a kitevőben. De azzal nem tudsz semmit se kezdeni. Igazából már Euler se tudott vele semmit kezdeni, csak feltűnt neki, hogy az olyan kifejezéseknek, melyekben n a kitevőben van, a limesze gyakran -lel és algebrai műveletekkel megadható, ezért a -et elnevezte magáról e-nek. Azóta általában az a feladat, hogy a kapott sorozatokat valahogy leredukáljuk erre a kifejezésre.
|
Előzmény: [730] Sinobi, 2013-10-20 01:12:11 |
|