|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Friss fórum:
|
|
|
|
A hét kérdése:
Jelentkezz be a heti kérdéshez!
|
|
|
|
Legolvasottabbak:
|
|
|
Euler
Hirdetés
| csiboy |
2004.08.19 14:52 | | 1754. |
| |
Es ha igy van nem lehetne, hogy legyen valami hirtelen otleted paros n-ekre is? |
|
| csiboy |
2004.08.19 14:51 | | 1753. |
|
| |
Vajon nem lehet, ha megvan mondjuk egy 7x7-re az alapmegoldas ahogy leirtad abbol szarmaztatni lehet az osszes megoldast az osszes lehetseges (also,felso) sorcsere es (elso,utolso) oszlopcsere osszes kombinaciojaval? |
|
| csiboy |
2004.08.19 14:42 | | 1752. |
|
| |
Imadom a hirtelen otleteidet. Szokas szerint nem ertem a bizonyitast, de hogy mukodik az biztos. Hmmm, nem semmi. Meg ha nem is kezdunk ha-val mondatot! Ha tudnad mennyit gorcsoltem mar rajta pedig :) |
|
| csiboy |
2004.08.19 14:31 | | 1751. |
|
| |
Igen a feladat az lenne, hogy tetszoleges n*n-es matrixban az osszes, feltetelnek megfelelo, matrixot megtalalni. Ha egy lenne meg az is jo lenne, de az osszes lenne az igazi. Feltetel meg az, hogy az n*n-es matrixban az 1..n-ig szamsor az ami szerepeljen, mert manualis megoldasnal nagyon zavaro lenne ha nem ez lenne es a megoldas sem annyira szep. |
|
| catchkoo |
2004.08.19 14:13 | | 1750. |
|
| |
Egy hirtelen ötlettel minden 3-mal nem osztható páratlan n-re tudok néhány ilyen mátrixot generálni :)
1,2,3,... n-2,n-1,n
3,4,5,... n, 1, 2
5,6,7,...
.
n,1,2,...
2,3,4,...
.
n-1,n,1,...
A 3-mal nem osztható azért kell, hogy a főátlóban az 1,4,7,... sorozat végigmenjen minden számon. Ekkor viszont a rejtett átlókban is teljesül a feltétel, másképp mondva bármely oszlopot illetve sort áttehetsz az egyik széléről a másikra.
Az lenne a feladat, hogy sokat, netán az összeset akarod megkapni mindne n-re? |
|
| csiboy |
2004.08.19 11:57 | | 1748. |
|
| |
Eddig a level. Szoval ez volna a nagy kerdes. Egyebkent ha ezek mennek akkor terbeli matrixokra is lehetne altalanositani, franko kis feladatokat lehetne csinalni. Ha ez megvolna catchkoo akkor van meg egy par akadaly amit elkene gorgetni. |
|
| csiboy |
2004.08.19 11:56 | | 1747. |
|
| |
Koszi a matrixokat, ezek mar megvannak, de a megfejteseket nagyon jo hogy elkuldted. A feladat amivel kuzdok tulajdonkeppen az volna, hogy tetszoleges n*n-es matrix generalasa az adott feltetelekkel (minden sor, minden oszlop, atlokban adott
n-es szamsor pontosan egyszer). Az otletet tulajdonkeppen az elso feladatod adta, ugyanis nagyon tetszenek ezek a tipusu feladatok, es gondoltam megorvendeztetek vele masokat is, ha egy igazan combos mondjuk 9x9-es matrixot alkotok. Csakhogy!
Eleg huzos problemaba utkoztem, ugyanis mar egy 7x7 matrix osszes lehetseges felirasa is gondot okoz, mert ez nyilvan tartalmazza azokat is amelyek nekunk kellenek, irdatlan nagy gepidot venne igenybe a roppant nagy variacio miatt es igy nem tudtam letrehozni. Par matematika tanar es azok matematikus ismeroseit is raallitottam a dologra, hogy esetleg tudna valaki valami olyan matematikai modszert amivel egzakt modon meg lehetne hatarozni ezeket a matrixokat az adot n*n-esek tomegebol. Eloszor gondoltam megkerulom a dolgot es programbol megkonstrualom az osszes matrixot majd kivalasztom belole a megfelelot, de amint irtam mar 7*7-re se vegezne tobb emberolto alatt sem. :( Arra mar kesz van a program egy modositott valtozata,
hogy egy adott letezo megoldas nehany kulcs erteket megadva (amik itt is szerepeltek), kiszamolja belole az egesz matrixot, ha azt lehetseges kikovetkeztetni egymas utani egyertelmu lepesek sorozataval. Na ehhez kellettek a matrixok es meg johetnek is. Ez elvileg
mukodik tetszoleges n*n-re. De az igazi az lenne ha magam is elo tudnek allitani ilyen matrixokat. 5*5-re megy, 6*6-ra par milliardig elmentem azok kozott nem talalt, hetesre meg eleve remenytelen. Lehet feldobom hatha catchkoonak van valami otlete, de attol tartok vagy melyebb linearis algebra ismeret szuksegeltetik hozza vagy van valami olyan trivialis megoldas amit mar a magatol erthetodosege miatt nem latok. Amennyiben neked volna valamilyen otleted nagyon megkoszonnem, ezert is kertem meg a forrasait a feladatnak hatha van valami szo arrol, hogyan lehetne ezeknek a matrixoknak az eloallitasat algoritmizalni....
|
|
| csiboy |
2004.08.19 11:53 | | 1746. |
|
| |
A kihivast vegulis yoda par korabbi feladata adta.
Bemasolom egyik feladat szoveget majd leirom az altalam kigondolta altalanositast.
10 perccel kesobb...
Nah nem talaltam meg de bemasolom a Yodanak irt levelem egy reszletet, meg leirok egy feladatot.
***************Feladat******
Adott egy tetszoleges 7*7-es matrix. Feladat ugy kitolteni, hogy minden sora es minden oszlopa es a ket atlo pontosan egyszer tartalmazza a 1...n itt most 1...7 ig szamokat.
*******Feladat vege*******
Ez volt a feladat ebbol gondoltam, hogy altalanosan is meg kene oldani a feladatot de, hogy vilagos legyen
mit is szeretnek bemasolom egy korabbi levelem yodanak: |
|
| csiboy |
2004.08.19 11:52 | | 1745. |
|
| |
Tobb reszletbe kuldom mert valami karakterhiba van benne es nem talalom :). |
|
| catchkoo |
2004.08.19 11:02 | | 1743. |
|
| |
Mondjad. |
|
| csiboy |
2004.08.19 10:50 | | 1742. |
|
| |
Kicsit eldurvultatok latom. Inkabb nekem segitenetek van egy matematikai problemam, amihez mar keves vagyok. |
|
| catchkoo |
2004.08.19 10:13 | | 1741. |
|
| |
Az ott található bizonyítás jó. Benne van az a lépés, amit hiányoltam, nevezetesen bebizonyítja, hogy ha E maximális, akkor az elhagyásával kapott gráf nem összefüggő, tehát van olyan komponense, aminek tényleg kevesebb pontja van G-nél. Így már alkalmazhatja az indukciós feltételt. |
|
| yoda |
2004.08.18 18:22 | | 1739. |
| |
nem, amiből másoltam az nem hivatalosan kiadott jegyzet (viszont abból vizsgáztam), úgyhogy lehet benne hiba. de persze a hivatalos jegyzetben is. A könyveket nálunk nemszokás megvenni, mert fentvan minden a weben is..
Hivatalosnak mondható az egyik előadó, Sali Attila vetítése:
http://www.cs.bme.hu/~sali/bsz2_1ho.pdf
|
|
| catchkoo |
2004.08.18 18:19 | | 1738. |
|
| |
Biztos, hogy a jegyzetben pontszám szerinti indukció van? Ezt valaki jegyezetelte, vagy hivatalosan kiadott anyag? Egyébként kinek az előadása és hol? |
|
| catchkoo |
2004.08.18 18:14 | | 1737. |
|
| |
"Seholse látom, hogy G'-nek kevesebb pontja van? G gráfból elhagyod az E élsorozatot és így kapott gráfot hívod G'-nek."
Avval indul, hogy a bizonyítás, hogy G pontszámára vonatkozó teljes indukciót alkalmaz. Ez azt jelenti, hogy
1. Valamilyen kicsi pntszámig minden esetről külön belátjuk, hogy arra igaz az állítás. Ez jelen esetben a hárönmszöges félmondat, arra majd külön válaszolok.
2 Feltesszük, hogy valamekkora pontszámig igaz (indukciós feltevés), és ezt felhasználva belátjuk hogy eggyel nagyobbra is igaz.
Jelen esetben az indukciós feltevés az, hogy G-nél kisebb pontszámú gráfokra az állítás igaz, hiszen G pontszámára vonatkozó indukciót alkalmazunk. Majd ezt a feltevést alkalmazzuk G' komponenseire azt állítva, hogy van bennük Euler-kör. Ez a lépés pedig hibás, mert G' állhat egy komponensből, amelynek ugyanannyi pontja van, mint G-nek, így nem alkalmazható rá az indukciós feltevés, tehát nem biztos, hogy van benne Euler-kör, márpedig ezt a bizonyítás felhasználja.
A pontszámra vonatkozó indukció helyett az élszámra vonatkozó indukcióval helyes lenne a bizonyítás. De ez az indukció is csak bonyolítaná a bizonyítást, semmi egyszerűsítést nem nyerünk vele.
Az egyszerű gráfokhoz nem értem miért ragaszkodsz. Persze, hogy van bennük kör, meg igaz rájuk a tétel, meg minden. De a tétel nem csak egyszerű gráfokról szól, te sem egyszerű gráfokra mondod ki és a bizonyítás sem használja ki sehol, hogy egyszerű gráfról van szó. És harmadszor is leírom, egyszerű gráfokra nem megy az a trükk, hogy
"
2 páratlan fokú pont: kössük össze ezeket egy újabb e éllel. A keletkező G' gráfban minden pont foka páros lesz, így az előző tétel értelmében van benne Euler-kör
"
Ha csak egyszerű gráfokra mondod ki a tételt, akkor ez a bizonyítás hibás, mert a plussz él behúzása után a gráf már nem lesz egszerű, így nem tudod, hogy van-e benne Euler kör. Tehát a bteljes bizonyítást általános gráfokra kell végezni, ekkor pedig ha ragaszkodunk a - most már élszám szerinti - indukcióhoz, akkor az 1 élű gráftól kell elindulni. (Egy pont, egy hurokél, tökéletes Euler-kör.) |
|
| yoda |
2004.08.18 18:13 | | 1736. |
|
| |
Várj, valamit nem értek. Seholse látom, hogy G'-nek kevesebb pontja van? G gráfból elhagyod az E élsorozatot és így kapott gráfot hívod G'-nek. Éleket hagyunk el, nem pontokat. Az egyszerű gráfban lehet kör. |
|
| catchkoo |
2004.08.18 18:12 | | 1735. |
|
| |
Lehet, hogy jegyzetből másoltad, de hibás.
Úgy kezdődik, hogy G PONTszámára való indukcióval bizonyítasz. Ez nem megy, mert a G' gráfnak nem lesz kevesebb pontja, tehát nem alkalmazható rá az indukciós feltevés.
A háromszög valóban a legkisebb ilyen egyszerű gráf, de a tétel nem csak egyszerű gráfokra igaz. Ezt ki is használod, hiszen egyszerű gráfokra hibás az Euler-útra vonatkozó bizonyítás, mert a plussz él behúzása után már nem lesz egyszerű.
Leírtam, hogy hogyan megy az utolsó lépés indukció nélkül, megpróbálom kicsit érthetőbben az egész bizonyítást:
Tehát G-nek csak páros fokú pontjai vannak. Legyen E egy maximális hosszúságú kör G-ben. Belátjuk, hogy E Euler-kör. Tegyük fel indirekten, hogy nem az, tehát G-nek van E-hez nem tartozó éle. Mivel G összefüggő, ezért olyan is van, aminek legalább az egyik végpontján átmegy E. Induljunk el ebből a közös pontból az adott élen csupa E-hez nem tartozó éleken át, amíg körbe nem érünk. Mivel G-ből E éleit elhagyva is csupa páros fokú pontunk marad, körbe fogunk érni. Ekkor az így bejárt kört E-hez hozzácsapva nagyobb kört kapunk, tehát E nem volt maximális.
Az indukció ahhoz kéne, hogy a kimaradó élekből Euler- kört tudjunk csinálni, ez azonban felesleges, hiszen bármilyen kicsi körrel bővítve E-t ellentmondást kapunk. |
|
| yoda |
2004.08.18 18:12 | | 1734. |
|
| |
"Nem a háromszög a legkisebb pontszámú ilyen gráf, a tétel nem csak egyszerű gráfokra igaz" a tétel a köröket bizonyítja, 2 pontú egyszerű gráfban nincs kör.
"A G' gráf komponenseinek miért van kevesebb pontja, mint G-nek?" Ez hogyan jött? Éle van kevesebb, mint pontja.
"Élszámra vonatkozó indukció már jobb lenne, de igaziból felesleges." Ezt, hogy csinálnád?
"egyébként jó az az algoritmus is, de ez kétségkívül szebb." Az igazsághoz hozzátartozik, hogy ez nem yoda-sejtés, és nem is yoda féle bizonyítás.. :) előadásjegyzetből másoltam ki |
|
| catchkoo |
2004.08.18 18:11 | | 1733. |
|
| |
"A legfeljebb 2 azért nem jó, nem pontos szerintem, mert abban benne van az is, hogy 1 lehet. "
That's not a bug, that's a feature! :)
A nem jó és a nem pontos között matematikai szempontból óriási szakadék tátong.
A szükséges feltételnek éppen az a lényege, hogy a feltételnek megfelelő esetekről SEMMIT nem állít, kizárólag a feltételnek nem megfelelő esetekről nyilatkozik.
Igenis megengedtem az 1-et, mert a megoldás szempontjából teljesen lényegtelen. Tőlem nyugodtan lehet 1! Nem használom ki, hogy nem lehet 1, tehát nem is mondom ki. Miért kéne kizárnom, amikor én a 4-et vizsgálom?
Nagy bajban lennénk, ha mindig a lehető legerősebb állítást kellen megfogalmaznunk, sok esetben épp az a matematika feladata, hogy megkeresse a még elégséges legegyszerűbb állításokat. Axiómarendszerek felállításakor például egyenesen követelmény, hogy ne fogalmazzunk meg erősebb állítást, mint amire feltétlenül szükségünk van.
Észrevételek a bizonyítással kapcsolatban.
Nem a háromszög a legkisebb pontszámú ilyen gráf, a tétel nem csak egyszerű gráfokra igaz (azokra nem lenne jó az Euler-útra vonatkozó bizonyítás, mi van, ha a két pont már össze van kötve?), az egy darab hurokélből álló gráfra is igaz az állítás, sőt az egy pontból álló, él nélküli, de még az üres gráfra is!
A G' gráf komponenseinek miért van kevesebb pontja, mint G-nek? Hiszen csak éleket hagytunk el és nem biztos, hogy több komponenst kapunk. Ha nincs kevesebb pontja, akkor nem alkalmazható rá az indukciós feltétel. Akkor viszont baj van, mert a G' gráfban talált körről kihasználjuk, hogy Euler-kör, különben nem biztos, hogy van közös pontja E-vel. Élszámra vonatkozó indukció már jobb lenne, de igaziból felesleges.
Ha E nem Euler kör, akkor van olyan pont, amin E áthalad és indul ki belőle E-hez nem tartozó él. Induljunk el ezen az élen, körbe fogunk érni, ezt a kört hozzácsaphatjuk E-hez tehát E nem maximális.
Most végiggondolva az én bizonyítási ötletemből is csak ez a mozzanat hiányzott, mármint, hogy a körök összefüggnek egymással, egyébként jó az az algoritmus is, de ez kétségkívül szebb. |
|
| yoda |
2004.08.18 18:10 | | 1732. |
|
| |
A legfeljebb 2 azért nem jó, nem pontos szerintem, mert abban benne van az is, hogy 1 lehet. (de egy valóban nem lehet, mert...)
Kör bizonyítása:
Egy összefüggő G gráfban akkor és csak akkor van Euler-kör, ha G minden pontjának fokszáma páros.
Biz.: Szükséges feltétel: triviális (Ha végigmegyünk az Euler-körön minden csúcsba "egyszer bemegyünk, egyszer kijövünk").
Elégséges: G pontszámára való indukcióval. A háromszög a legkisebb pontszámú ilyen gráf, erre igaz. Tegyük fel, hogy minden G-nél kisebb pontszámú gráfra igaz az állítás.
Létezik zárt élsorozat: Induljunk el a gráf egy tetszőleges pontjából, és haladjunk az élek mentén úgy, hogy egy élen kétszer nem megyünk át. Ha olyan pontba érünk, amelyből nem vezet ki olyan él, amelyen még nem haladtunk át, akkor ez csak a kiindulópont lehet, mivel minden pont foka páros. Válaszzuk ki a zárt élsorozatok közül a maximálisat, nevezzük E-nek, ez Euler-kör. Indirekt tegyük fel, hogy E nem egy Euler-köre G-nek. Vizsgáljuk a G' gráfot, amelyet úgy kapunk, hogy a G gráfból elhagyjuk az E-ben szereplő éleket. Ha E nem Euler kör, akkor G' nem csak izolált pontokból áll, hanem vannak benne komponensek, ráadásul ezekben minden fokszám páros (zárt sétát hagytunk el), tehát az indukciós feltevés alapján ezekben biztosan van Euler kör. Ekkor viszont E nem a maximális zárt élsorozat volt: E és a komponens közös pontjából elindulva végigjárhatjuk a komponenst, majd E-t. Vagyis E valóban Euler-kör. |
|
| catchkoo |
2004.08.18 18:09 | | 1731. |
|
| |
A legfeljebb 2 miért ne lenne helyes akkor is, ha eszembe sem jut, hogy 1 nem lehet? Az, hogy a legfeljebb 2 szükséges, könnyen bizonyítható. Ennek a szükséges feltételnek a 4 nem felel meg. A feladat megoldva. Sehol nem használtam ki azt, hogy az 1-et is (sőt a -1-et is :) ) megengedtem, holott akár ki is zárhattam volna.
Egy ötlet az Euler kör létezésének bizonyítására. Az nyilvánvaló, hogy az élek halmaza felbontható véges sok körre. Ezeket kellene egy szuszra bejárni. Induljunk el valahonnan és ha egy olyan körrel találkozunk, amin még nem jártunk, térjünk át arra. Ha egy kör végéhez értünk, akkor folytassuk az utunkat azon a körön, amin ebbe a pontba érkeztünk. Evvel a stratégiával végig fogjuk járni az összes kört, végül a kiindulási pontba visszaérve. |
|
| yoda |
2004.08.18 18:08 | | 1730. |
|
| |
Érdekességképp bemásolom, hogy hogyan mondják ki most, és a bizonyítást (kihagyom a kör bizonyítását). Persze mindkét variáció helyes, ha tudod, hogy miért.
Euler-út létezésének tétele:
Egy összefüggő G gráfban akkor és csak akkor van Euler-út, ha a páratlan fokú pontok száma 0 vagy 2.
Biz.:
Szükségesség: triviális (Ha végigmegyünk az Euler-úton minden csúcsba "egyszer bemegyünk, egyszer kijövünk").
Elégségesség:
0 páratlan fokú pont: Euler-kör tétele.
2 páratlan fokú pont: kössük össze ezeket egy újabb e éllel. A keletkező G' gráfban minden pont foka páros lesz, így az előző tétel értelmében van benne Euler-kör, ami a definíció szerint tartalmazza az e élet is. Hagyjuk el ebből az Euler-körből az e élet, így egy Euler-utat kaptunk G-ben. |
|
| catchkoo |
2004.08.18 18:07 | | 1729. |
|
| |
A szükséges feltétel az, hogy LEGFELJEBB 2 legyen.
Az pedig egy ettől független tétel, hogy a páratlan fokú pontok száma páros, tehát az 1 nem tud előállni. De ez nem része a szükséges feltételnek!!! Mivel MINDEN olyan gráf, amelyben 1 darab páratlan fokú pont van, lerajzolható egy vonallal, ezért jelen esetben nehézkes és tökéletesen felesleges lenne még külön bizonyítani azt is, hogy az 1 eset nem tud előállni.
Ha viszont valaki az általad írt formában mondja ki a feltételt, akkor kutya kötelessége úgy is bizonyítani. Ez nem nehéz de lényegesen kevésbé elegáns, mint azt mondani, hogy legfeljebb a két végpont lehet páratlan, ennél több biztosan nem. Nekem nem volt kedvem feleslegesen magyarázkodni, pedig igazán nem vádolhatsz avval, hogy szűkszavú vagyok a szükséges indoklások terén.
Emlékeim szerint az igazi tétel úgy szól, hogy
Annak, hogy egy gráfnak legyen minden élét pontosan egyszer tartalmazó útja, SZÜKSÉGES ÉS ELÉGSÉGES feltétele, hogy a páratlan fokú pontok száma legfeljebb kettő legyen.
(Az elégségesség bizonyítása már nem ilyen pofonegyszerű.)
Ha ezt a tételt is úgy mondanád ki, hogy 0 vagy 2, az kifejezetten félrevezető lenne. |
|
| yoda |
2004.08.18 18:06 | | 1728. |
|
| |
nem legfeljebb, hanem 0 v 2 |
|
| catchkoo |
2004.08.18 18:05 | | 1727. |
|
| |
Általában az igaz, hogy ha egy összefüggő töröttvonal kezdő és végpontját, valamint önmagával vett metszéspontjait tekintjük csúcspontoknak, akkor az egy vonallal való lerajzolásnak szükséges feltétele, hogy azoknak a csúcspontoknak a száma, amelyekből páratlan irányba lehet elindulni, legfeljebb 2 legyen. Ilyen csúcspont ugyanis csak a kezdő és a végpont lehet. Mivel a négyzet két átlóval négy ilyen pontot határoz meg, nem lehet lerajzolni egy vonallal. |
|
| yoda |
2004.08.18 18:04 | | 1726. |
|
| |
catchkoo-val belekavarodtunk az Euler út, kör bizonyítás bizonyításába, és úgy gondoltuk, hogy a beszélgetésünket megosztjuk veletek is, várjuk a hozzászólásokat meg mindenféle..
Aki nemismerné a gráfok alapjait:
G gráfban Euler-útnak nevezünk egy olyan összefüggő élsorozatot, ami pontosan egyszer tartalmazza a G összes élét. Ha az élsorozat zárt, akkor Euler-kört kapunk. (az Euler-út nem igazi út a gráfban, mert egy pontot többször is tartalmazhat, hivatalosan sétának nevezhetjük, ugyanígy az Euler-kör zárt séta.)
Gráfot pedig képzeljük el úgy, hogy vannak pontok, amik vonalakkal össze vannak kötve. Ezek a vonalak a gráf élei, a pontok pedig a pontjai..
sorban az írások: |
|
|
|
|
