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.
"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.
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ó).
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.
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.
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.
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.
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.
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.
"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.)
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.
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)