Annihilation(G)

[katjamarina]

Pozdravljeni, bi nama lahko pomagali pri kodi za računanje Annihilation(G), ker nama ne vrne pravega števila. Ko gre v zanki po k-jih, pogleda ali je vsota še manjša od "vel" in potem še prišteje k, čeprav je potem vsota že večja, kar pa ni v redu, vendar pa tega ne znava popraviti.

def annihilation(G): 
    stopnje = degrees(G)
    seznam = []
    vel = int(sum(stopnje)/2)
    sest = 0
    for k in stopnje:
        while sest== vel or sest < vel:
            seznam.append(k)
            sest += k
    max_k = len(seznam) - 1
    return max_k

Hvala za odgovor in lep pozdrav.

[jaanos]

Znotraj zanke for imata še zanko while, zaradi česar se prišteva le prva stopnja v seznamu.

Pravzaprav je seznam nepotreben, saj potrebujeta le njegovo dolžino. Zanko bi torej lahko napisala tako:

    for i, k in enumerate(stopnje):
        sest += k
        if sest > vel:
            return i

V vsakem koraku se torej prišteje stopnja, in ko ta vsota preseže polovico skupne, se vrne trenutni indeks (indeksiranje začne pri 0, tako da je to ravno število predhodnih korakov).

Naj opozorim še, da bo zanka šla do konca, če graf nima povezav. Po definiciji je Annihilation(G) v tem primeru enak kar številu vozlišč grafa G, tako da lahko po koncu zanke to vrneta, da pokrijeta še ta primer.

[katjamarina]

Pozdravljeni, Še nekaj naju zanima. To je najina koda: https://cocalc.com/share/a899536a-bb4e-45ab-acc0-bf87a0c6d624/2018-11-19-204938.sagews?viewer=share Ko hočeva preveriti testiranje_domneve(1), nama sporoči napako, ko pa poskusiva z drugimi števili, pa dela. Je to kaj narobe?

[katjamarina]

Sva našla napako v total_domination_number, in sedaj dela.