Deljeno kromatično število

[MancaStrgar]

Pri iskanju deljenega kromatičnega števila imam težave. Na povezavi je vidmo, kaj sem naredila do sedaj: https://cocalc.com/share/f2f7d7cf-3047-495e-86cc-25e9c4844e6a/deljeno%20kromati%C4%8Dno%20%C5%A1tevilo.sagews?viewer=share Naredila sem matriko A, ki mi deluje pravilno. Le v primeru Knesrjevega grafa, mi ne deluje pravilno, ker imamo množice znotraj množic in ne vem kako naj potem tukaj definiram matriko A. Problem pa imam tudi infimumu, ne vem kako deluje v sageu in kako naj definiram y, da bo potem vrnilo pravi rezultat. Hvala za pomoč.

[jaanos]

Najprej, trenutni program ne bo nujno našel vseh maksimalnih neodvisnih množic (kar počne, je nekakšno požrešno grajenje neodvisne množice za vsako začetno vozlšče). V skladu z #2 bi šlo nekako tako:

def maksimalne_neodvisne_mnozice(G, A, B):
    if len(B) == 0:
        mnozice.append(A)
    for v in B:
        C = A + Set([v])
        if C in pregledane:
            continue
        pregledane.add(C)
        maksimalne_neodvisne_mnozice(G, C, B - G[v] - [v])

Potem lahko za graf G spravita najdene neodvisne množice v seznam mnozice:

mnozice = []
pregledane = set()
maksimalne_neodvisne_mnozice(G, Set(), Set(G))

Naj opozorim, da ima ta algoritem eksponentno časovno zahtevnost (navsezadnje je iskanje maksimalne neodvisne množice NP-težek problem), tako da za večje grafe ne bo končal v doglednem času. Za KneserGraph(5, 2) (kar je Petersenov graf na 10 vozliščih) bo tako šlo, Dyckov graf (32 vozlišč) pa je verjetno prevelik.

Če imata graf G, katerega vozlišča niso zaporedna števila od 0 naprej (kot je to pri Kneserjevih grafih), lahko z ukazom G.relabel() zamenjata oznake vozlišč - potem bo mogoče vozlišča uporabiti kot indekse matrike.

Infumum pa lahko (ker imata končne grafe) pri reševanju linearnega programa nadomestita z minimumom.