Keresés

Részletes keresés

Dr.Feelgood Creative Commons License 2004.01.09 0 0 922

ps-hez ghostscript/ghostview,
dvi-hez pl. Yap, ha windowsos vagy.
Előzmény: ADtranz Incentro (921)
ADtranz Incentro Creative Commons License 2004.01.09 0 0 921
Bocsánat, hogy ide írom, de még mindig van néhány formátum, amit nem tudok olvasni (szerencsére a .gz-re már rájöttem, hogy mi):

.dvi
.ps

Ez utóbbi nagyon fontos lenne. Nem tudjátok hol lehet hozzá letölteni programot, ami olvasni tudja?

Köszönöm:
ADtranz

Gergo73 Creative Commons License 2004.01.06 0 0 920
Valóban, és igy hangzik Kuratowski tétele. Amit én mondtam, az Wagner változata.
Előzmény: KoporShow (918)
Törölt nick Creative Commons License 2004.01.06 0 0 919
Bocs, tényleg, csak nem tetted egyértelművé, hogy ez nem csak a személyes véleményed, hanem tudod is.
Előzmény: KoporShow (913)
KoporShow Creative Commons License 2004.01.06 0 0 918
Mellesleg nem csak minorral, hanem topologikus reszgraffal (azaz olyan reszgraffal, amely homeomorf K5-hoz, vagy K3,3-hoz) is igaz Kuratowski tetele.
Előzmény: Gergo73 (915)
ADtranz Incentro Creative Commons License 2004.01.06 0 0 917
Bocs, hülyeséget kérdeztem... ;)
Előzmény: ADtranz Incentro (916)
ADtranz Incentro Creative Commons License 2004.01.06 0 0 916
De ha feltesszük, hogy minden csúcs foka minimum 3, akkor már részgráfokkal is igaz lesz a tétel?
Előzmény: Gergo73 (915)
Gergo73 Creative Commons License 2004.01.06 0 0 915
A Kuratowski-tétel nem K5 és K3,3 részgráfokat, hanem K5 és K3,3 minorokat zár ki. Tehát ha a K5 egy élére ráteszel mondjuk 100 adalék csúcsot (ami által az él egy 101 hosszú úttá változik), akkor a kapott gráf továbbra sem lesz sikba rajzolható, sőt nem is lehet részgráfja egyetlen sikgráfnak sem.
Előzmény: ADtranz Incentro (914)
ADtranz Incentro Creative Commons License 2004.01.06 0 0 914
"temérdek olyan gráf van, aminek nincs K5 részgráfja, de nem is síkbarajzolható"

Igen, a Kuratowski-tétel a K5-ön kívül egy másik típusú részgráf létezését is kizárja síkbarajzolható gráfoknál.
Egyébként a feladat szerintem szép, néhány speciális esetét már megoldottam (kombinatorikus geometriával - tkp. tényleg kombinatorikusan;)).

"Egyébként a feladat sokkal egyszerűbbnek tűnik, mint a kérdéseid"

Nem tudtam, hogy bonyolultat kérdezek.:-)
Viszont ha lenne rájuk egyszerű szabály, valszeg a bizonyítás ezek segítségével is körülményes volna. Itt a "kombinatorikust" úgy értettem, hogy külön megvizsgálom, hogy hány nem izomorf adott tulajdonságú gráf van, illetve hány olyan, amiben van adott számú kígyó. Minthogy az izomorfia-vizsgálatra nincs egyszerű algoritmus, ezért ezt a fajta megoldást szerintem elvethetem.

Előzmény: Gergo73 (912)
KoporShow Creative Commons License 2004.01.06 0 0 913
Lenyegeben en is ezt irtam.
Előzmény: Törölt nick (907)
Gergo73 Creative Commons License 2004.01.06 0 0 912
Nem tudom, mit értesz kombinatorikus megoldás alatt, de én biztos vagyok benne, hogy kombinatorikus a megoldás ;-) Egyébként a feladat sokkal egyszerűbbnek tűnik, mint a kérdéseid (amikkel kapcsolatban megjegyzem, hogy temérdek olyan gráf van, aminek nincs K5 részgráfja, de nem is sikbarajzolható).
Előzmény: ADtranz Incentro (910)
zepp Creative Commons License 2004.01.06 0 0 911
Kazaa:-)
Előzmény: Törölt nick (909)
ADtranz Incentro Creative Commons License 2004.01.05 0 0 910
Köszönöm a válaszokat!

Az összefüggőséget a válaszok alapján tudom ellenőrizni, de a többit nem.

Az eredeti feladat a következő:

Adott egy összefüggő, egyszerű gráf, amelynek nincs ötödrendű teljes részgráfja, és minden pont foka minimum 2. Egy (minden ponton legfeljebb egyszer áthaladó) vonalat kígyónak nevezünk, ha abból, hogy két ponton a vonal keresztülhalad, és a két pont között van él, következik, hogy a vonal a két pont közötti élen halad. Legkevesebb hány egymással nem találkozó kígyó kell ahhoz, hogy együtt a gráf minden pontját lefedjék?

Először kombinatorikus megoldással próbálkoztam, ezért kérdeztem meg ezeket, de ezek alapján a kombinatorikus megoldás gyak. kivitelezhetetlennek tűnik.

Nem gondoltam volna, hogy ezek az egyszerűnek tűnő problémák is ennyire bonyolultak.

Törölt nick Creative Commons License 2004.01.05 0 0 909
Hol "találtál" MATHEMATICÁt?
Előzmény: zepp (908)
zepp Creative Commons License 2004.01.05 0 0 908
Köszi, közben találtam Mathematica-t, felraktam, szép, jó, bonyolult...elég:)
Előzmény: Pugfan (906)
Törölt nick Creative Commons License 2004.01.05 0 0 907
Nem mutatták még meg sem azt, hogy P-ben van, sem, hogy NP-teljes. A sejtés, hogy egyik sem igaz, és külön komplexitási osztályt definiáltak graph isomorphism complete-névvel.
Előzmény: KoporShow (905)
Pugfan Creative Commons License 2004.01.05 0 0 906
Előzmény: zepp (894)
KoporShow Creative Commons License 2004.01.05 0 0 905
A grafizomorfia nagy valoszinüseggel nem NP-teljes, mert akkor öszzeomlana egy bonyolultsagi hierarhia. Viszont valoszinüleg nem is polinomialis.
Előzmény: Gergo73 (900)
Gergo73 Creative Commons License 2004.01.05 0 0 904
Végül 1974-ben Hopcroft-Wong a sikgráfok izomorfiaproblémájára is adott O(n) lépésszámú algoritmust.
Előzmény: Gergo73 (903)
Gergo73 Creative Commons License 2004.01.05 0 0 903
Kicsit utánanéztem az irodalomnak. Hopcroft-Tarjan mintegy 30 éve adott O(n) lépésszámú algoritmust annak eldöntésére, hogy egy n csúcsú gráf sikbarajzolható-e, továbbá O(nlog(n)) lépésszámú algoritmust annak eldöntésére, hogy két tetszőleges n csúcsú sikgráf izomorf-e.
Előzmény: Gergo73 (900)
sashimi Creative Commons License 2004.01.05 0 0 902
Osszefuggesre cn2-nel alt. nem lehet jobb alg: osszuk az n csucsot ket egyforma A es B halmazra, A es B teljes graf, de A es B kozott nincs el. Ekkor az algoritmusnak minden A es B kozotti elre ra kell kerdeznie.

sashimi

Előzmény: Gergo73 (900)
KoporShow Creative Commons License 2004.01.05 0 0 901
A grafok izomorfiaproblemajara nagy valoszinüseggel nem letezik polinomialis algoritmus. Trivialis algoritmusok, amik minden lehetseges csucslekepezest kiprobalnak persze letenek, de az altalanos esetben nem tul hatekonyak.

A sikbarajzolhatosag eldöntesere vannak gyors (polnomialis) moszerek. Az egyik peldaul Tutte modszere, amely ugy müködik, hogy keres az ember egy lapot (egy kört emi egy sik beagyazalsaban egy oldalt ad meg, aztan ennek alapjan megkonstrualja graf egy baricentrikus beagyazasat.)

A leszamlalasi probelmadat nem ismerem, de a pontos szamot kiszamolni, nagy valoszinüseggel nem lehet esszerü idön belül, nem beszelve zart formularol.

Előzmény: ADtranz Incentro (898)
Gergo73 Creative Commons License 2004.01.05 0 0 900
1. Tutte 1962-ben igazolta, hogy az n csúcsú maximális (azaz 3n-6 éllel rendelkező) sikgráfok száma izomorfia erejéig aszimptotikusan konstansszor (256/27)nn-5/2. Ebből azonnal adódik, hogy az n csúcsú sikgráfok száma izomorfia erejéig legfeljebb (2048/27)n (ha n elég nagy). Másfelől Osthus-Prömel-Taraz egy tavaly publikált cikke szerint az n csúcsú sikgráfok száma izomorfia erejéig legalább 26.17n (ha n elég nagy). Ennek a dolgozatnak az eredményei alapján valószinűnek tartom, hogy majdnem minden n csúcsú sikgráfnak cn éle van (ahol 0<c<3 konstans), és ezzel az n csúcsú sikgráfok száma minden bizonnyal (256/27+o(1))nbinom(3n-6,cn).

2. Az összefüggőségre könnyen adható polinomiális algoritmus (egy fix csúcstól 1,2,stb. távolságra levő csúcsok listája rekurzivan megtalálható). Az izomorfia felismerése nem NP-teljes probléma? A sikbarajzolhatóságra nem tudom a választ, de Kuratowski tétele alapján valószinűsitem, hogy van polinomiális algoritmus.

Előzmény: ADtranz Incentro (898)
hekke Creative Commons License 2004.01.05 0 0 899
"1. Hány különböző (=semmelyik 2 sem izomorf) n-edrendű síkbarajzolható, összefüggő, egyszerű gráf létezik?"
Passz. (Sok, szerintem O(2^(n^2)) és o(2^n)között valahol. (Az alsó eléggé hasraütésszerűen.))
"2. Adott egy gráf (szomszédsági) mátrixa. Hogyan lehet a lehető legegyszerűbb módon eldönteni a mátrix alapján, hogy a gráf
-síkbarajzolható?
-összefüggő?
-illetve két mátrixról eldönteni, hogy azokhoz izomorf gráfok tartoznak?"
síkbarajzolható: Nem biztos, hogy van erre egyszerű algoritmus (, de algoritmus van).
összefüggő: veszed (n-1)-edik és n-edik hatványát, (vagy (I+A)^n-t) és megnézed, hogy a főátlón kívül van-e 0 eleme. Ha van, akkor nem öf. (Szerintem ez a leghatékonyabb (ha szomszédsági mátrixunk van), ha a gyors mátrixszorzást (Strassen alg.) használjuk, abból a gyorshatványozással.)
izomorfak-e: Jobb ötlet híján (nekem nincs jobb ötletem, másnak lehet, de tudtommal ez "nehéz", eddig hatékony algoritmust nem látott probléma) permutálod a sorokat, oszlopokat, és megnézed, hogy azonosat kaptál-e. Speciálisan összefüggő, síkbarajzolható gráfokra (esetleg egy síkbarajzolással) nem lennék meglepve, ha lenne egy sokkal hatékonyabb algoritmus.
Gondolom másnak sokkal naprakészebb, pontosabb tudása van. (Ezért elnézést, ha hülyeségeket írtam volna.)
Előzmény: ADtranz Incentro (898)
ADtranz Incentro Creative Commons License 2004.01.05 0 0 898
Szükségem lenne a segítségetekre ezekben a kérdésekben:

1. Hány különböző (=semmelyik 2 sem izomorf) n-edrendű síkbarajzolható, összefüggő, egyszerű gráf létezik?

2. Adott egy gráf (szomszédsági) mátrixa. Hogyan lehet a lehető legegyszerűbb módon eldönteni a mátrix alapján, hogy a gráf
-síkbarajzolható?
-összefüggő?
-illetve két mátrixról eldönteni, hogy azokhoz izomorf gráfok tartoznak?

Ha fentiekre tudomásotok, vagy véleményetek szerint nincs egyszerű, zárt formula, légyszi azt is írjátok le.

Köszönöm:
ADtranz

zepp Creative Commons License 2004.01.05 0 0 897
Izé, köszi a tippet, megnézem nem lehet-e szerezni belőle egy "olcsó" példányt:-)
Előzmény: zepp (896)
zepp Creative Commons License 2004.01.05 0 0 896
Félmillió forintért?

Vmi freeware-re gondoltam:)

Előzmény: sashimi (895)
sashimi Creative Commons License 2004.01.05 0 0 895
Mathematica.

sashimi

Előzmény: zepp (894)
zepp Creative Commons License 2004.01.05 0 0 894
Sziasztok!

Olyan programot keresek, ami tud függvényeket ábrázolni, akár kettőnél több dimenzióban is:-) Szóval valami olyan okosság kéne nekem, ami rajzol nekem pl. olyat hogy y=(x1-5)2+(x2-5)2, vagy olyat hogy y=aKbLc, meg hasonlók.

(némi keresés után úgy tűnt h talán itt a legkevésbé off a kérdésem)

Gergo73 Creative Commons License 2004.01.05 0 0 893
Kis javitás: 0<=a1<=a2<=...<=an és 0<=b1<=b2<=...<=bn.
Előzmény: Gergo73 (892)

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!