Algoritem

[jonagricar]

Pozdravljeni, s Tjašo imava nekaj težav z algoritmom in sicer z delom, kjer bi definirali funkcijo za tree(G). Ne razumeva ravno kaj to je in imava zato težave tudi s samo konstrukcijo. Kako bi se najlažje tega lotili oziroma kaj predlagate vi?

CoCalc link: https://cocalc.com/share/16f90892-0564-437e-a17d-81bef1e50456/2018-10-28-113315.sagews?viewer=share

Hvala za odgovor in lep pozdrav!

[jaanos]

Kot sem že razložil @tjasamehle, je tree(G) velikost največje podmnožice vozlišč grafa G, ki inducira drevo - torej da je graf na izbranih vozliščih in vseh povezavah med njimi povezan in brez ciklov. Za primer si poglejta MancaStrgar/-Fractional-chromatic-number-and-fractional-clique-number-of-a-graph#3.

Za izračun tega števila bo najverjetneje najlažje uporabiti backtracking, torej rekurzivno preiskovanje. Ideja bi tukaj bila, da napišeta funkcijo, ki sprejme trenutno drevo (oz. množico njegovih vozlišč) in množico kandidatov za razširitev (torej vozlišč, ki so sosedna natanko enemu vozlišču iz drevesa). Če je velikost drevesa večja od trenutno največjega, potem to število ustrezno povečata, nato pa za vsakega od kandidatov naredi novo drevo in izračuna novo množico kandidatov (tj., doda med kandidate sosede novega vozlišča, ki niso že v drevesu in niso že sosedi katerega od njih, in odstrani tiste kandidate, ki so tudi sosedi novega vozlišča - smiselno bi bilo torej vzdrževati še množico vozlišč, ki imajo vsaj dva soseda v drevesu) ter se rekurzivno pokliče.

Da potem dobita tree(G), pokličeta svojo funkcijo na vsakem vozlišču in množico njegovih sosedov kot kandidati. Da se izogneta večkratnim preiskovanjem istih dreves, svetujem, da si hranita tudi množico že pregledanih dreves, in rekurzivni klic končata, če je bilo drevo že pregledano.

[jaanos]

Še ena opomba: za drugo najmanjšo stopnjo trenutno uporabita indeks 2 v obrnjenem seznamu - ker se indeksiranje začne pri 0, bo to tretja najmanjša stopnja. Lahko tudi uporabita indeks 1, ali pa na neobrnjenem seznamu uporabita indeks -2.

Mimogrede, s prof. Škrekovskim sva razmišljala, ali second smallest degree pomeni drugi vnos v seznamu, ali pa drugi vnos v seznamu vrednosti (torej brez ponovitev). Glede na zapis na strani z domnevo, bi sklepal, da gre za prvo interpretacijo (kar poskušata dobiti). Če bosta našli kak protiprimer, svetujem, da preverita, ali je še vedno protiprimer, če namesto drugega vnosa uporabita drugo najmanjšo vrednost (razlika bo seveda le, če se prva dva vnosa razlikujeta).

[jonagricar]

Skonstruirali sva kodo za tree(G), vendar v nekaterih primerih ne deluje oziroma vrne napačno številko, kaj bi lahko bilo narobe? https://cocalc.com/share/16f90892-0564-437e-a17d-81bef1e50456/2018-10-28-113315.sagews?viewer=share

In pa še nekaj v zvezi z girth(G). Ali res velja, da če je graf brez cikla potem je girth avtomatično neskončno? Če je to res, potem domnevo ovržemo pri vsakem grafu brez cikla?

[jaanos]

Vrednost tree(G) dobita z rekurzivnim preiskovanjem. Šlo bi nekako tako:

def tree(G):
    drevesa = set()
    def tree_backtrack(T, S, X):
        velikost = len(T)
        for v in S:
            TT = T + Set([v])
            if TT in drevesa:
                continue
            drevesa.add(TT)
            N = Set(G[v])
            SS = (S ^^ N) - TT - X
            XX = X + (S & N)
            velikost = max(velikost, tree_backtrack(TT, SS, XX))
        return velikost
    return max(tree_backtrack(Set([u]), Set(G[u]), Set()) for u in G)

Množica drevesa hrani že pregledane množice vozlišč (da ne bi istih množic preiskovali večkrat) - njeni elementi imajo Sage-ov tip Set, ki predstavlja nespremenljive množice in ga je za razliko od Pythonovega tipa set mogoče uporabiti kot elemente množic (ali ključe slovarjev). Pomožna funkcija tree_backtrack sprejme tri argumente - trenutno drevo T, množico kandidatov S (tj., vozlišča z natanko enim sosedom v T), in množico prepovedanih vozlišč X (tj., vozlišča z več kot enim sosedom v T). Za vsakega kandidata se potem poračunajo nove množice - tukaj operacije +, -, & in ^^ predstavljajo unijo, razliko, presek in simetrično razliko množic.

Naj opozorim, da ima ta algoritem eksponentno časovno zahtevnost, tako da za večje grafe ne bo končal v doglednem času.

Ožina grafa brez ciklov (če je graf povezan, potem je to drevo) je res navadno definirana kot neskončnost, kar pomeni, da domneva za drevesa ne drži. To lahko vsekakor napišeta v poročilo, a vseeno domnevo še preverita na grafih, ki niso drevesa (torej imajo vsaj en cikel). Druga interpretacija bi sicer bila, da ožina za drevesa ni definirana, in potem enako velja tudi za to domnevo.