Egy konkrét végtelen gráf: pontjai legyenek az összes turing-gépek állapotai, két pont (A és B) össze van kötve, ha van olyan turing-gép amelynek 2 egy más utáni állapota A és B. Legyen egy kitüntetett pont S. (Stop) - Ebbe jut minden turing-gép megálláskor.
Nincs olyan turing-gép, amelyik a fenti gráf bármely pontja és S közötti összeköttetés meglétét eldönthetné (hiszen akkor a megállási probléma megoldható volna)
Igen én is ezt okoskodtam ki, a kérdésem tkp az lett volna, hogy mivel ezt az algoritmust már jó régen feltalálhatta valaki, mi a probléma és az algoritmus neve. Vagy túl triviális vagy túl speciális probléma?
>>>>Mondjuk nem tudom, hogy a végtelen gráfok a gráfelmélet részének tekinthetőek-e. Szerintem nem, hanem a megadástól függően más-más matekot igényelnek. >>>
Tipikusan nem. Mármint vannak gráfelmélészek akik ilyesmit csinálnak, de a végtelen gráfos emberek nagy része valszámos, analizises vagy csoportelmélész indíttatású.
„Nyilván van olyan algoritmus, ami ebben az esetben biztosan megáll”
(vagyis ha két pont között van véges út)
Ja, még annyit hozzátennék, hogy ha nem tudunk semmit a végtelen gráf megadási módjáról, akkor még azt sem tudhatjuk, hogy egy pont szomszédjait véges lépésben meg lehet-e határozni. (még véges szomszéd esetén sem)
„Vegtelen grafok eseten elofordulhat, hogy ez az 'algoritmus' soha nem all meg, ha nincs ut a ket adott pont kozott.”
…vagy ha ez az út végtelen.
Ha van véges út, akkor meg algoritmusfüggő, hogy biztosan megáll-e. Nyilván van olyan algoritmus, ami ebben az esetben biztosan megáll, de nem biztos, hogy ez a (valamilyen értelemben) legjobb algoritmus.
Mondjuk nem tudom, hogy a végtelen gráfok a gráfelmélet részének tekinthetőek-e. Szerintem nem, hanem a megadástól függően más-más matekot igényelnek.
Olyan algoritmust, amely garantaltan megall, es megmondja, hogy van-e ut ket pont kozott nem tudok mondani
Az a sejtesem, hogy bizonyithato, hogy nem letezhet ilyen algoritmus, (bar ahogy mondtam, eloszor tisztatni kell, hogy hogyan van vegesen megfogalmazva a vegtelen graf.)
En egyszeruen csak az egyik pontbol terjeszkednek:
1. lepesben meghatarozom az egy lepesbol elerheto pontok halmazat
2. lepesben meghatarozom az 2 lepesbol elerheto pontok halmazat
...
Ha az n. lepesben a halmazban benne van a masik pont, akkor a lepeseket visszakovetve megvan a legrovidebb (n hosszu) ut.
Ha nincs a halmazban az masik pont, akkor tudhato, hogy a legrovidebb ut legalabb n+1 hosszu, vagy nem letezik ut a ket pont kozott.
Vegtelen grafok eseten elofordulhat, hogy ez az 'algoritmus' soha nem all meg, ha nincs ut a ket adott pont kozott.
Olyan algoritmust, amely garantaltan megall, es megmondja, hogy van-e ut ket pont kozott nem tudok mondani, bar gondolom ebben az esetben az is erdekes, hogy hogyan van megadva a vegtelen graf. (Hiszen nyilvan minden megfogalmazhato vegtelen grafnak van egy veges megadasa. Nem?)
Elindulsz a két pontból hulllámterjedéssel és amikor összeérnek, akkor megvan a legrövidebb út.
Nem kell bejárni hozzá minden pontot, kivéve, ha a gráf nem összefüggő és két komponensből áll (bár ekkor is le lehet állni, amikor az egyik komponensről ez kiderül).
Sziasztok. Lenne egy kérdésem. Mi a neve annak a problémának, amivel szembenállok, és milyen algoritmusok vannak rá: Van egy végtelen nagyságú gráf. Adott két pont. Találjuk meg a legrövidebb utat ( nem kell bejárni minden pontot!)
Eloszoris, meg kell kulonboztetni el- es csucstranzitiv grafokat. Ezen kivul van meg a tranzitivitasnak kulonbozo erosebb valtozatai: peldaul minden tetszoleges n-hosszu ut atviheto akarmelyik masikba egy automorfizmussal.
A tranzitiv grafok egeszen mas fajta modszereket igenyelnek mint a sik grafok. Specialis esetekben (adott fokszam, tranzitivatasi fok, + feltetelek) le lehet irni az osszes feltetelt kielegito grafot explicite. Altalaban azonban nem tudok mas tetlrol, ami a tranzitivitassal ekvivalens, attol lenyesen kulonbozo kriteriumot adna. Azt biztosra tudom, hogy arra nincs polinomialis futasideju algoritmus, ami egy grafrol eldontene, hogy (el/csucs)-tranzitiv e. Valoszinu olyan algoritmus sincs ami kiszamolna egy graf automorfizmus-csoportjat, de meg olyan sincs, ami ket grafrol eldontene, hogy izomorfak e.
A szimmetrikus/tranzitiv grafok temakore egyebkent a grafelmelet es csoportelmelet hatarterulete. Minden csoport es egy tetszoleges veges reszhalmaza definial ugyanis egy szimmetrikus (tranzitiv) grafot. (Un. Cayley graf). A tranzitiv grafok tanulmanyozasa legalabb annyira csoportelmelet mint grafelmelet.
Nyilván ilyenek a teljes gráfok, a szabályos testek, az intervallum-gráfok, a Turán-féle gráfok, stb. (Egy érdekesebb kérdés: a G3,3, azaz a három ház-három kút gráf ilyen-e?)
De a végtelen fa pont nem, úgyhogy szvsz valami másra gondolhatott notwe.
Nyilván ilyenek a teljes gráfok, a szabályos testek, az intervallum-gráfok, a Turán-féle gráfok, stb. (Egy érdekesebb kérdés: a G3,3>/sub>, azaz a három ház-három kút gráf ilyen-e?)
De a végtelen fa pont nem, úgyhogy szvsz valami másra gondolhatot notwe.
> Tudsz olyan gráfot, amelyben a pontok és egy adott pontból kiinduló élek is teljesen megkülönböztethetetlenek? Kb. mint a
végtelen fa, csak valamivel érdekesebbet! Köszi!
Mit szolsz ket ponthoz, amik egy ellel vannak osszekotve?
Ha a kerdesedet jol ertem, akkor te tranzitiv grafokra gondolsz, amiben akarmelyik ket csucs atviheto egy izomorfiaval egy masikba, es ugyanez az elekre is igaz.
Egyebekent az osszes kor is ilyen.
Nagyobb fokszamra (azaz ahol minden csucsban n el talakozik) is lehet peldakat mondani, de annak komoly elmelete van. A grafok automorfizmuscsoprtjaival kiterjedt kutatasi terulet.
