Bojanje vrhova i bridova grafa u SAGE-u. Sparivanje u grafu.

verzija: SageMath 8.4

Planarni grafovi

$K_{2,3}$ je planarni graf

In [1]:
K23=graphs.CompleteBipartiteGraph(2,3)
K23.is_planar()
Out[1]:
True
In [2]:
K23.show()

neko planarno smještenje od $K_{2,3}$

In [3]:
poz=K23.layout_planar();poz
Out[3]:
{0: [3, 1], 1: [0, 3], 2: [1, 0], 3: [1, 1], 4: [1, 2]}
In [4]:
K23.show(pos=poz)

možemo i direktno dobiti sliku bez posebnog računanja pozicija vrhova

In [5]:
K23.show(layout='planar')

$K_{3,3}$ nije planarni graf

In [6]:
graphs.CompleteBipartiteGraph(3,3).is_planar()
Out[6]:
False

$K_5$ nije planarni graf

In [7]:
graphs.CompleteGraph(5).is_planar()
Out[7]:
False

Petersenov graf nije planarni graf

In [8]:
graphs.PetersenGraph().is_planar()
Out[8]:
False

$K_4$ je planarni graf

In [9]:
graphs.CompleteGraph(4).is_planar()
Out[9]:
True
In [10]:
graphs.CompleteGraph(4).show()

neko ravninsko smještenje od $K_4$

In [11]:
graphs.CompleteGraph(4).show(layout='planar')

Platonova tijela

In [12]:
tijela = tetrahedron((0,-3.5,0), color='blue') + cube((0,-2,0),color=(.25,0,.5)) +\
      octahedron(color='red') + dodecahedron((0,2,0), color='orange') +\
      icosahedron(center=(0,4,0), color='yellow')
In [13]:
tijela.show(aspect_ratio=[1,1,1],frame=False,viewer='threejs',online=True)

Kocka

3D tijelo

In [14]:
cube(color='yellow',frame=False,viewer='threejs',online=True)
Out[14]:

pripadni graf

In [15]:
graphs.CubeGraph(3).show(vertex_labels=False,layout='spring')

neko planarno smještenje

$\nu=8,  \varepsilon=12,  \Phi=6,\quad \nu-\varepsilon+\Phi=2$

In [16]:
graphs.CubeGraph(3).show(vertex_labels=False,vertex_size=50,layout='planar')

3D graf

In [17]:
graphs.CubeGraph(3).show3d(viewer='threejs',online=True)

Tetraedar

3D tijelo

In [18]:
tetrahedron(color='yellow',frame=False,viewer='threejs',online=True)
Out[18]:

pripadni graf

In [19]:
graphs.TetrahedralGraph().show(vertex_labels=False,layout='spring')

neko planarno smještenje

$\nu=4,  \varepsilon=6,  \Phi=4,\quad \nu-\varepsilon+\Phi=2$

In [20]:
graphs.TetrahedralGraph().show(vertex_labels=False,layout='planar')

3D graf

In [21]:
graphs.TetrahedralGraph().show3d(viewer='threejs',online=True)

Oktaedar

3D tijelo

In [22]:
octahedron(color='yellow',frame=False,viewer='threejs',online=True)
Out[22]:

pripadni graf

In [23]:
graphs.OctahedralGraph().show(vertex_labels=False,layout='spring')

neko planarno smještenje

$\nu=6,  \varepsilon=12,  \Phi=8,\quad \nu-\varepsilon+\Phi=2$

In [24]:
graphs.OctahedralGraph().show(vertex_labels=False,vertex_size=40,layout='planar')

3D graf

In [25]:
graphs.OctahedralGraph().show3d(viewer='threejs',online=True)

Dodekaedar

3D tijelo

In [26]:
dodecahedron(color='pink',frame=False,viewer='threejs',online=True)
Out[26]:

pripadni graf

In [27]:
graphs.DodecahedralGraph().show(vertex_labels=False,vertex_size=40,layout='spring')

neko planarno smještenje

$\nu=20,  \varepsilon=30,  \Phi=12,\quad \nu-\varepsilon+\Phi=2$

In [28]:
graphs.DodecahedralGraph().show(vertex_labels=False,vertex_size=20,layout='planar',figsize=(7,7))

možemo dobiti i ljepše planarno smještenje uz pametnije poredane vrhove

In [29]:
pozicijeDOD={0:[0.546, 0.956], 1:[0.144, 0.65], 2:[0.326, 0.188], 3:[0.796, 0.188], \
19:[0.988, 0.646], 10:[0.552, 0.814], 8:[0.264, 0.616], 6:[0.404, 0.296], \
4:[0.752, 0.298], 18:[0.846, 0.624], 9:[0.43, 0.692], 11:[0.682, 0.692], \
17:[0.758, 0.492], 5:[0.566, 0.358], 7:[0.364, 0.484], 13:[0.504, 0.602], \
12:[0.608, 0.602], 16:[0.634, 0.51], 15:[0.566, 0.444], 14:[0.48, 0.51]}
In [30]:
graphs.DodecahedralGraph().show(pos=pozicijeDOD,vertex_size=150)

3D graf

In [31]:
graphs.DodecahedralGraph().show3d(viewer='threejs',online=True)

Ikozaedar

3D tijelo

In [32]:
icosahedron(color='yellow',frame=False,viewer='threejs',online=True)
Out[32]:

pripadni graf

In [33]:
graphs.IcosahedralGraph().show(vertex_labels=False,vertex_size=40)

neko planarno smještenje

$\nu=12,  \varepsilon=30,  \Phi=20,\quad \nu-\varepsilon+\Phi=2$

In [34]:
graphs.IcosahedralGraph().show(vertex_labels=False,vertex_size=20,layout='planar')

3D graf

In [35]:
graphs.IcosahedralGraph().show3d(viewer='threejs',online=True)

Zadatak

Ispitajte da li je zadani graf planarni i u slučaju da jest pronađite jedno njegovo ravninsko smještenje.

Rješenje

In [36]:
H=Graph({1:[2,5,6],2:[3,4,5],3:[4,5,6],4:[5],5:[6]})

Zadani graf jest planarni

In [37]:
H.is_planar()
Out[37]:
True

jedno njegovo ravninsko smještenje

In [38]:
H.show(layout='planar')

Bojanje vrhova grafa

Na početku ćemo implementirati tri algoritma za pohlepno bojanje vrhova grafa koje ćemo kasnije koristiti u zadacima zajedno s već implementiranim SAGE metodama za bojanje vrhova grafa. Pohlepno bojanje vrhova ne daje općenito bojanje vrhova s minimalnim brojem boja. Svi algoritmi su randomizirani u smislu da ako u nekom koraku imaju više mogućnosti izbora da na slučajni način odaberu neku od mogućnosti. Na primjer, kod Welsh-Powellovog algoritma kod silaznog sortiranja vrhova, ukoliko više vrhova imaju isti stupanj, tada se oni na slučajni način rasporede jedan za drugim. Kod Brelazovog algoritma, ukoliko više vrhova imaju isti stupanj zasićenosti, tada se na slučajni način odabere jedan od tih vrhova.

Pomoćne funkcije

Funkcija bojanje_vrha pridružuju vrhu $w$ najmanji mogući prirodni broj (boju) s obzirom na trenutno već obojane vrhove koji su spremljeni u rječnik boje. Funkcija stupanj_zasicenosti računa stupanj zasićenosti vrha $w$ s obzirom na trenutno obojane vrhove koji su spremljeni u rječnik boje. Stupanj zasićenosti vrha $w$ s obzirom na trenutno obojane vrhove je maksimalni broj različitih boja s kojima su trenutno obojani (neki ili možda svi) njegovi susjedi.

In [39]:
def bojanje_vrha(graf,w,boje):
    obojaniSusjedi=list(set(graf.neighbors(w)).intersection(set(boje.keys())))
    trazenjeBoje=[]
    for u in obojaniSusjedi.__iter__():
        trazenjeBoje.append(boje[u])
    if set(boje.values()).difference(set(trazenjeBoje))!=set([]):
        boje[w]=min(set(boje.values()).difference(set(trazenjeBoje)))
    else:
        boje[w]=max(boje.values())+1
    return None
In [40]:
def stupanj_zasicenosti(graf,w,boje):
    obojaniSusjedi=list(set(graf.neighbors(w)).intersection(set(boje.keys())))
    brojBoja=len(set(map(lambda x:boje[x],obojaniSusjedi)))
    return brojBoja

Random bojanje

Daje pohlepno bojanje vrhova tako da vrhove boja unaprijed slučajno odabranim redoslijedom. Na izlazu sa vraća uređena trojka. Prva komponenta je lista u kojoj je dan redoslijed bojanja vrhova. Druga komponenta je rječnik u kojem su ključevi vrhovi, a vrijednosti ključeva su boje vrhova (boje su prirodni brojevi). Treća komponenta je ukupni broj različitih boja koje su upotrijebljenje za bojanje vrhova.

In [41]:
def random_bojanje(graf):
    vrhovi=graf.vertices()
    shuffle(vrhovi)
    obojaniVrhovi=[vrhovi[0]]
    boje={vrhovi[0]:1}
    del vrhovi[0]
    
    while vrhovi != []:
        w = vrhovi[0]
        bojanje_vrha(graf,w,boje)
        obojaniVrhovi.append(w)
        del vrhovi[0]
        
    return (obojaniVrhovi, boje, len(set(boje.values())))

Welsh Powell

Daje pohlepno bojanje vrhova tako da vrhove najprije sortira padajuće po njihovom stupnju i zatim ih boja tim redoslijedom. Na izlazu sa vraća uređena trojka. Prva komponenta je lista u kojoj je dan redoslijed bojanja vrhova. Druga komponenta je rječnik u kojem su ključevi vrhovi, a vrijednosti ključeva su boje vrhova (boje su prirodni brojevi). Treća komponenta je ukupni broj različitih boja koje su upotrijebljenje za bojanje vrhova.

In [42]:
def Welsh_Powell(graf):
    vrhovi=graf.vertices()
    vrhovi_sorted=[]
    while vrhovi != []:
        D=max(graf.degree(vrhovi))
        max_vrh=[]
        for v in vrhovi.__iter__():
            if graf.degree(v)==D: max_vrh=max_vrh+[v]
        shuffle(max_vrh)
        vrhovi_sorted.extend(max_vrh)
        vrhovi=list(set(vrhovi).difference(set(max_vrh)))    
    
    obojaniVrhovi=[vrhovi_sorted[0]]
    boje={vrhovi_sorted[0]:1}
    del vrhovi_sorted[0]
    while vrhovi_sorted != []:
        w = vrhovi_sorted[0]
        bojanje_vrha(graf,w,boje)
        obojaniVrhovi.append(w)
        del vrhovi_sorted[0]
        
    return (obojaniVrhovi, boje, len(set(boje.values())))

Brelaz

Daje pohlepno bojanje vrhova Brelazovim algoritmom. Na izlazu sa vraća uređena trojka. Prva komponenta je lista u kojoj je dan redoslijed bojanja vrhova. Druga komponenta je rječnik u kojem su ključevi vrhovi, a vrijednosti ključeva su boje vrhova (boje su prirodni brojevi). Treća komponenta je ukupni broj različitih boja koje su upotrijebljenje za bojanje vrhova.

In [43]:
def Brelaz(graf):
    vrhovi=graf.vertices()
    D=max(graf.degree())
    max_vrh=()
    for v in vrhovi.__iter__():
        if graf.degree(v)==D: max_vrh=max_vrh+(v,)
    v1=choice(max_vrh)
    obojaniVrhovi=[v1]
    boje={v1:1}
    del vrhovi[vrhovi.index(v1)]
    
    while vrhovi != []:
        #racunanje stupnjeva zasicenosti
        ds={}
        for v in vrhovi.__iter__():
            ds[v]=stupanj_zasicenosti(graf,v,boje)
        #izdvajanje vrhova s maksimalnim stupnjem zasicenosti
        ds_max=max(ds.values())
        ds_maxVrh=()
        for v in ds:
            if ds[v]==ds_max: ds_maxVrh=ds_maxVrh+(v,)
        w=choice(ds_maxVrh)
        #bojanje vrha s maksimlnim stupnjem zasicenosti
        bojanje_vrha(graf,w,boje)
        obojaniVrhovi.append(w)
        del vrhovi[vrhovi.index(w)]
    
    return (obojaniVrhovi, boje,  len(set(boje.values())))

Zadatak

U tablici se nalazi popis od 10 studentica zajedno s kolegijima koje su odabrale.

studentica  odabrani kolegiji
Marija Fizika, Matematika, Engleski
Janja Fizika, Geografija, Ekonomija
Ivana Geografija, Poslovanje
Ana Statistika, Ekonomija
Lana Matematika, Poslovanje
Sandra Fizika, Geografija
Danijela Poslovanje, Statistika
Katarina Matematika, Geografija
Petra Fizika, Plivanje, Statistika
Dijana Fizika, Ekonomija, Plivanje

Neki od kolegija se mogu istovremeno predavati. Međutim, želimo li svakoj od studentica omogućiti nesmetano slušanje svih kolegija koje je odabrala, koliko najmanje različitih vremenskih termina predavanja moramo staviti u raspored?

Rješenje

Formiramo graf u kojemu su vrhovi svi spomenuti kolegiji, a dva vrha su spojena bridom ako i samo ako postoji studentica koja je upisala oba pripadna kolegija. Najmanji broj termina je tada jednak kromatskom broju tog grafa.

In [44]:
G1=Graph({"fizika":["matematika","engleski","geografija","ekonomija","plivanje","statistika"], 
          "matematika":["engleski","poslovanje","geografija"], 
          "geografija":["ekonomija","poslovanje"], 
          "statistika":["ekonomija","poslovanje","plivanje"], 
          "ekonomija":["plivanje"]})
In [45]:
G1.show(layout="circular",vertex_size=3700,figsize=(5,5))

Kromatski broj grafa je 4 pa su potrebna najmanje 4 različita termina.

In [46]:
G1.chromatic_number()
Out[46]:
4

Jedan mogući razmještaj predmeta u termine (elementi particije vrhova predstavljaju termine, a dva predmeta se izvode u istom terminu ako i samo ako pripadaju istom elementu te particije, tj. ako i samo ako imaju istu boju).

In [47]:
G1.coloring()
Out[47]:
[['geografija', 'engleski', 'plivanje'],
 ['statistika'],
 ['ekonomija', 'matematika'],
 ['fizika', 'poslovanje']]

želimo li to prikazati vizualno na samom grafu

In [48]:
bojanje1=G1.coloring(hex_colors=True);bojanje1
Out[48]:
{'#00ffff': ['geografija', 'engleski', 'plivanje'],
 '#7f00ff': ['statistika'],
 '#7fff00': ['fizika', 'poslovanje'],
 '#ff0000': ['ekonomija', 'matematika']}
In [49]:
G1.show(layout="circular",vertex_size=3700,figsize=(5,5),vertex_color=bojanje1)

Zašto se promatrani graf ne može obojati s manje od 4 boje? Zato jer postoji 4-klika {ekonomija,fizika,plivanje,statistika}.

In [50]:
G1.clique_number()
Out[50]:
4
In [51]:
G1.clique_maximum()
Out[51]:
['ekonomija', 'fizika', 'plivanje', 'statistika']

i samo je jedna takva najveća klika u promatranom grafu

In [52]:
G1.cliques_maximum()
Out[52]:
[['ekonomija', 'fizika', 'plivanje', 'statistika']]

Pogledajmo malo kako se ponašaju algoritmi za pohlepno bojanje vrhova na zadanom grafu.

U 50 pokretanja pohlepnog algoritma sa slučajnim rasporedom bojanja vrhova, dogodilo se da algoritam nije uvijek dao bojanje vrhova s minimalnim brojem boja (naravno, nije se to moralo dogoditi u prvih 50 izvođenja, možda se moglo dogoditi tek nakon 100 izvođenja algoritma). Napravite eksperiment tako da sve implementirane algoritme za pohlepno bojanje na zadanom grafu pokrenete na primjer 10 000 puta i pogledajte što se događa. Da li Brelaz i Welsh-Powell daju na ovom grafu uvijek bojanje vrhova s minimalnim brojem boja?

In [53]:
for k in xrange(50):
    print random_bojanje(G1)

(['engleski', 'statistika', 'poslovanje', 'matematika', 'ekonomija', 'plivanje', 'geografija', 'fizika'], {'statistika': 1, 'matematika': 3, 'geografija': 1, 'ekonomija': 2, 'poslovanje': 2, 'plivanje': 3, 'engleski': 1, 'fizika': 4}, 4)
(['plivanje', 'engleski', 'ekonomija', 'geografija', 'matematika', 'fizika', 'poslovanje', 'statistika'], {'statistika': 4, 'matematika': 2, 'geografija': 1, 'ekonomija': 2, 'poslovanje': 3, 'plivanje': 1, 'engleski': 1, 'fizika': 3}, 4)
(['matematika', 'ekonomija', 'poslovanje', 'geografija', 'statistika', 'engleski', 'fizika', 'plivanje'], {'statistika': 3, 'matematika': 1, 'geografija': 3, 'ekonomija': 1, 'poslovanje': 2, 'plivanje': 2, 'engleski': 2, 'fizika': 4}, 4)
(['geografija', 'poslovanje', 'statistika', 'matematika', 'fizika', 'ekonomija', 'engleski', 'plivanje'], {'statistika': 1, 'matematika': 3, 'geografija': 1, 'ekonomija': 3, 'poslovanje': 2, 'plivanje': 4, 'engleski': 1, 'fizika': 2}, 4)
(['matematika', 'poslovanje', 'plivanje', 'fizika', 'ekonomija', 'statistika', 'engleski', 'geografija'], {'statistika': 4, 'matematika': 1, 'geografija': 4, 'ekonomija': 3, 'poslovanje': 2, 'plivanje': 1, 'engleski': 3, 'fizika': 2}, 4)
(['plivanje', 'poslovanje', 'engleski', 'geografija', 'fizika', 'ekonomija', 'matematika', 'statistika'], {'statistika': 2, 'matematika': 4, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 1, 'engleski': 1, 'fizika': 3}, 4)
(['matematika', 'plivanje', 'statistika', 'geografija', 'poslovanje', 'engleski', 'fizika', 'ekonomija'], {'statistika': 2, 'matematika': 1, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 3, 'plivanje': 1, 'engleski': 2, 'fizika': 3}, 4)
(['poslovanje', 'ekonomija', 'statistika', 'geografija', 'matematika', 'fizika', 'plivanje', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 1, 'poslovanje': 1, 'plivanje': 3, 'engleski': 1, 'fizika': 4}, 4)
(['engleski', 'geografija', 'plivanje', 'fizika', 'poslovanje', 'ekonomija', 'statistika', 'matematika'], {'statistika': 4, 'matematika': 3, 'geografija': 1, 'ekonomija': 3, 'poslovanje': 2, 'plivanje': 1, 'engleski': 1, 'fizika': 2}, 4)
(['fizika', 'plivanje', 'geografija', 'statistika', 'engleski', 'matematika', 'poslovanje', 'ekonomija'], {'statistika': 3, 'matematika': 3, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 2, 'engleski': 2, 'fizika': 1}, 4)
(['geografija', 'ekonomija', 'statistika', 'engleski', 'matematika', 'fizika', 'poslovanje', 'plivanje'], {'statistika': 1, 'matematika': 2, 'geografija': 1, 'ekonomija': 2, 'poslovanje': 3, 'plivanje': 4, 'engleski': 1, 'fizika': 3}, 4)
(['engleski', 'statistika', 'geografija', 'poslovanje', 'ekonomija', 'fizika', 'matematika', 'plivanje'], {'statistika': 1, 'matematika': 4, 'geografija': 1, 'ekonomija': 2, 'poslovanje': 2, 'plivanje': 4, 'engleski': 1, 'fizika': 3}, 4)
(['ekonomija', 'statistika', 'matematika', 'poslovanje', 'plivanje', 'fizika', 'geografija', 'engleski'], {'statistika': 2, 'matematika': 1, 'geografija': 2, 'ekonomija': 1, 'poslovanje': 3, 'plivanje': 3, 'engleski': 2, 'fizika': 4}, 4)
(['fizika', 'ekonomija', 'plivanje', 'engleski', 'poslovanje', 'geografija', 'statistika', 'matematika'], {'statistika': 4, 'matematika': 4, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 3, 'engleski': 2, 'fizika': 1}, 4)
(['statistika', 'poslovanje', 'matematika', 'plivanje', 'ekonomija', 'fizika', 'geografija', 'engleski'], {'statistika': 1, 'matematika': 1, 'geografija': 5, 'ekonomija': 3, 'poslovanje': 2, 'plivanje': 2, 'engleski': 2, 'fizika': 4}, 5)
(['geografija', 'plivanje', 'engleski', 'statistika', 'poslovanje', 'ekonomija', 'matematika', 'fizika'], {'statistika': 2, 'matematika': 2, 'geografija': 1, 'ekonomija': 3, 'poslovanje': 3, 'plivanje': 1, 'engleski': 1, 'fizika': 4}, 4)
(['matematika', 'plivanje', 'statistika', 'geografija', 'poslovanje', 'engleski', 'fizika', 'ekonomija'], {'statistika': 2, 'matematika': 1, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 3, 'plivanje': 1, 'engleski': 2, 'fizika': 3}, 4)
(['matematika', 'fizika', 'ekonomija', 'engleski', 'geografija', 'statistika', 'poslovanje', 'plivanje'], {'statistika': 3, 'matematika': 1, 'geografija': 3, 'ekonomija': 1, 'poslovanje': 2, 'plivanje': 4, 'engleski': 3, 'fizika': 2}, 4)
(['matematika', 'statistika', 'poslovanje', 'geografija', 'ekonomija', 'plivanje', 'engleski', 'fizika'], {'statistika': 1, 'matematika': 1, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 2, 'plivanje': 3, 'engleski': 2, 'fizika': 4}, 4)
(['ekonomija', 'poslovanje', 'engleski', 'geografija', 'statistika', 'matematika', 'fizika', 'plivanje'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 1, 'poslovanje': 1, 'plivanje': 3, 'engleski': 1, 'fizika': 4}, 4)
(['geografija', 'poslovanje', 'matematika', 'fizika', 'engleski', 'ekonomija', 'statistika', 'plivanje'], {'statistika': 1, 'matematika': 3, 'geografija': 1, 'ekonomija': 3, 'poslovanje': 2, 'plivanje': 4, 'engleski': 1, 'fizika': 2}, 4)
(['statistika', 'matematika', 'engleski', 'plivanje', 'poslovanje', 'geografija', 'fizika', 'ekonomija'], {'statistika': 1, 'matematika': 1, 'geografija': 3, 'ekonomija': 5, 'poslovanje': 2, 'plivanje': 2, 'engleski': 2, 'fizika': 4}, 5)
(['engleski', 'plivanje', 'fizika', 'poslovanje', 'geografija', 'ekonomija', 'statistika', 'matematika'], {'statistika': 3, 'matematika': 4, 'geografija': 3, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 1, 'engleski': 1, 'fizika': 2}, 4)
(['engleski', 'poslovanje', 'matematika', 'ekonomija', 'plivanje', 'fizika', 'geografija', 'statistika'], {'statistika': 4, 'matematika': 2, 'geografija': 4, 'ekonomija': 1, 'poslovanje': 1, 'plivanje': 2, 'engleski': 1, 'fizika': 3}, 4)
(['engleski', 'statistika', 'poslovanje', 'geografija', 'ekonomija', 'plivanje', 'fizika', 'matematika'], {'statistika': 1, 'matematika': 3, 'geografija': 1, 'ekonomija': 2, 'poslovanje': 2, 'plivanje': 3, 'engleski': 1, 'fizika': 4}, 4)
(['matematika', 'ekonomija', 'statistika', 'geografija', 'fizika', 'poslovanje', 'engleski', 'plivanje'], {'statistika': 2, 'matematika': 1, 'geografija': 2, 'ekonomija': 1, 'poslovanje': 3, 'plivanje': 4, 'engleski': 2, 'fizika': 3}, 4)
(['matematika', 'poslovanje', 'statistika', 'geografija', 'plivanje', 'fizika', 'ekonomija', 'engleski'], {'statistika': 1, 'matematika': 1, 'geografija': 3, 'ekonomija': 5, 'poslovanje': 2, 'plivanje': 2, 'engleski': 2, 'fizika': 4}, 5)
(['engleski', 'statistika', 'ekonomija', 'poslovanje', 'matematika', 'geografija', 'plivanje', 'fizika'], {'statistika': 1, 'matematika': 3, 'geografija': 1, 'ekonomija': 2, 'poslovanje': 2, 'plivanje': 3, 'engleski': 1, 'fizika': 4}, 4)
(['plivanje', 'matematika', 'statistika', 'poslovanje', 'fizika', 'engleski', 'ekonomija', 'geografija'], {'statistika': 2, 'matematika': 1, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 3, 'plivanje': 1, 'engleski': 2, 'fizika': 3}, 4)
(['poslovanje', 'fizika', 'statistika', 'matematika', 'engleski', 'plivanje', 'ekonomija', 'geografija'], {'statistika': 2, 'matematika': 2, 'geografija': 3, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 3, 'engleski': 3, 'fizika': 1}, 4)
(['statistika', 'fizika', 'ekonomija', 'poslovanje', 'matematika', 'plivanje', 'geografija', 'engleski'], {'statistika': 1, 'matematika': 1, 'geografija': 4, 'ekonomija': 3, 'poslovanje': 2, 'plivanje': 4, 'engleski': 3, 'fizika': 2}, 4)
(['ekonomija', 'engleski', 'poslovanje', 'geografija', 'matematika', 'fizika', 'statistika', 'plivanje'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 1, 'poslovanje': 1, 'plivanje': 3, 'engleski': 1, 'fizika': 4}, 4)
(['statistika', 'plivanje', 'fizika', 'geografija', 'matematika', 'poslovanje', 'ekonomija', 'engleski'], {'statistika': 1, 'matematika': 2, 'geografija': 1, 'ekonomija': 4, 'poslovanje': 3, 'plivanje': 2, 'engleski': 1, 'fizika': 3}, 4)
(['statistika', 'engleski', 'matematika', 'plivanje', 'ekonomija', 'poslovanje', 'geografija', 'fizika'], {'statistika': 1, 'matematika': 2, 'geografija': 1, 'ekonomija': 3, 'poslovanje': 3, 'plivanje': 2, 'engleski': 1, 'fizika': 4}, 4)
(['plivanje', 'poslovanje', 'engleski', 'statistika', 'geografija', 'fizika', 'ekonomija', 'matematika'], {'statistika': 2, 'matematika': 4, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 1, 'engleski': 1, 'fizika': 3}, 4)
(['fizika', 'plivanje', 'ekonomija', 'poslovanje', 'matematika', 'engleski', 'statistika', 'geografija'], {'statistika': 4, 'matematika': 2, 'geografija': 4, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 2, 'engleski': 3, 'fizika': 1}, 4)
(['engleski', 'poslovanje', 'plivanje', 'statistika', 'ekonomija', 'fizika', 'matematika', 'geografija'], {'statistika': 2, 'matematika': 2, 'geografija': 5, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 1, 'engleski': 1, 'fizika': 4}, 5)
(['engleski', 'ekonomija', 'fizika', 'poslovanje', 'geografija', 'statistika', 'matematika', 'plivanje'], {'statistika': 3, 'matematika': 4, 'geografija': 3, 'ekonomija': 1, 'poslovanje': 1, 'plivanje': 4, 'engleski': 1, 'fizika': 2}, 4)
(['poslovanje', 'statistika', 'engleski', 'matematika', 'ekonomija', 'fizika', 'plivanje', 'geografija'], {'statistika': 2, 'matematika': 2, 'geografija': 4, 'ekonomija': 1, 'poslovanje': 1, 'plivanje': 4, 'engleski': 1, 'fizika': 3}, 4)
(['matematika', 'ekonomija', 'engleski', 'fizika', 'geografija', 'poslovanje', 'statistika', 'plivanje'], {'statistika': 2, 'matematika': 1, 'geografija': 2, 'ekonomija': 1, 'poslovanje': 3, 'plivanje': 4, 'engleski': 2, 'fizika': 3}, 4)
(['geografija', 'fizika', 'ekonomija', 'statistika', 'poslovanje', 'matematika', 'engleski', 'plivanje'], {'statistika': 1, 'matematika': 3, 'geografija': 1, 'ekonomija': 3, 'poslovanje': 2, 'plivanje': 4, 'engleski': 1, 'fizika': 2}, 4)
(['plivanje', 'ekonomija', 'geografija', 'fizika', 'engleski', 'poslovanje', 'matematika', 'statistika'], {'statistika': 4, 'matematika': 4, 'geografija': 1, 'ekonomija': 2, 'poslovanje': 2, 'plivanje': 1, 'engleski': 1, 'fizika': 3}, 4)
(['fizika', 'engleski', 'statistika', 'matematika', 'geografija', 'plivanje', 'ekonomija', 'poslovanje'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 3, 'engleski': 2, 'fizika': 1}, 4)
(['matematika', 'geografija', 'fizika', 'ekonomija', 'engleski', 'statistika', 'poslovanje', 'plivanje'], {'statistika': 2, 'matematika': 1, 'geografija': 2, 'ekonomija': 1, 'poslovanje': 3, 'plivanje': 4, 'engleski': 2, 'fizika': 3}, 4)
(['poslovanje', 'geografija', 'matematika', 'statistika', 'plivanje', 'fizika', 'ekonomija', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 1, 'engleski': 1, 'fizika': 4}, 4)
(['ekonomija', 'poslovanje', 'plivanje', 'geografija', 'fizika', 'statistika', 'matematika', 'engleski'], {'statistika': 4, 'matematika': 4, 'geografija': 2, 'ekonomija': 1, 'poslovanje': 1, 'plivanje': 2, 'engleski': 1, 'fizika': 3}, 4)
(['geografija', 'fizika', 'engleski', 'matematika', 'poslovanje', 'plivanje', 'statistika', 'ekonomija'], {'statistika': 3, 'matematika': 3, 'geografija': 1, 'ekonomija': 4, 'poslovanje': 2, 'plivanje': 1, 'engleski': 1, 'fizika': 2}, 4)
(['engleski', 'geografija', 'statistika', 'matematika', 'ekonomija', 'plivanje', 'poslovanje', 'fizika'], {'statistika': 1, 'matematika': 2, 'geografija': 1, 'ekonomija': 2, 'poslovanje': 3, 'plivanje': 3, 'engleski': 1, 'fizika': 4}, 4)
(['fizika', 'poslovanje', 'ekonomija', 'plivanje', 'statistika', 'matematika', 'geografija', 'engleski'], {'statistika': 4, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 3, 'engleski': 3, 'fizika': 1}, 4)
(['ekonomija', 'fizika', 'matematika', 'statistika', 'poslovanje', 'engleski', 'geografija', 'plivanje'], {'statistika': 3, 'matematika': 1, 'geografija': 3, 'ekonomija': 1, 'poslovanje': 2, 'plivanje': 4, 'engleski': 3, 'fizika': 2}, 4)
In [54]:
for k in xrange(10):
    print Welsh_Powell(G1)

(['fizika', 'ekonomija', 'matematika', 'geografija', 'statistika', 'poslovanje', 'plivanje', 'engleski'], {'statistika': 3, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 4, 'engleski': 3, 'fizika': 1}, 4)
(['fizika', 'ekonomija', 'geografija', 'statistika', 'matematika', 'plivanje', 'poslovanje', 'engleski'], {'statistika': 3, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 4, 'engleski': 3, 'fizika': 1}, 4)
(['fizika', 'ekonomija', 'statistika', 'geografija', 'matematika', 'plivanje', 'poslovanje', 'engleski'], {'statistika': 3, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 4, 'engleski': 3, 'fizika': 1}, 4)
(['fizika', 'geografija', 'ekonomija', 'matematika', 'statistika', 'plivanje', 'poslovanje', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 4, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'matematika', 'geografija', 'statistika', 'ekonomija', 'plivanje', 'poslovanje', 'engleski'], {'statistika': 2, 'matematika': 2, 'geografija': 3, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 3, 'engleski': 3, 'fizika': 1}, 4)
(['fizika', 'geografija', 'statistika', 'matematika', 'ekonomija', 'poslovanje', 'plivanje', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 4, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'statistika', 'geografija', 'matematika', 'ekonomija', 'plivanje', 'poslovanje', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 4, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'ekonomija', 'matematika', 'statistika', 'geografija', 'poslovanje', 'plivanje', 'engleski'], {'statistika': 3, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 4, 'engleski': 3, 'fizika': 1}, 4)
(['fizika', 'statistika', 'geografija', 'ekonomija', 'matematika', 'poslovanje', 'plivanje', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 4, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'ekonomija', 'matematika', 'geografija', 'statistika', 'plivanje', 'poslovanje', 'engleski'], {'statistika': 3, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 4, 'engleski': 3, 'fizika': 1}, 4)
In [55]:
for k in xrange(10):
    print Brelaz(G1)

(['fizika', 'plivanje', 'statistika', 'ekonomija', 'geografija', 'matematika', 'poslovanje', 'engleski'], {'statistika': 3, 'matematika': 3, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 2, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'matematika', 'engleski', 'geografija', 'ekonomija', 'poslovanje', 'plivanje', 'statistika'], {'statistika': 4, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 3, 'engleski': 3, 'fizika': 1}, 4)
(['fizika', 'statistika', 'ekonomija', 'plivanje', 'geografija', 'matematika', 'poslovanje', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 4, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'ekonomija', 'plivanje', 'statistika', 'geografija', 'matematika', 'poslovanje', 'engleski'], {'statistika': 4, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 3, 'engleski': 3, 'fizika': 1}, 4)
(['fizika', 'ekonomija', 'geografija', 'plivanje', 'statistika', 'matematika', 'poslovanje', 'engleski'], {'statistika': 4, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 3, 'engleski': 3, 'fizika': 1}, 4)
(['fizika', 'plivanje', 'statistika', 'ekonomija', 'geografija', 'matematika', 'poslovanje', 'engleski'], {'statistika': 3, 'matematika': 3, 'geografija': 2, 'ekonomija': 4, 'poslovanje': 1, 'plivanje': 2, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'geografija', 'ekonomija', 'statistika', 'plivanje', 'matematika', 'engleski', 'poslovanje'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 4, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'statistika', 'ekonomija', 'plivanje', 'geografija', 'matematika', 'poslovanje', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 4, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'statistika', 'ekonomija', 'plivanje', 'geografija', 'matematika', 'poslovanje', 'engleski'], {'statistika': 2, 'matematika': 3, 'geografija': 2, 'ekonomija': 3, 'poslovanje': 1, 'plivanje': 4, 'engleski': 2, 'fizika': 1}, 4)
(['fizika', 'matematika', 'geografija', 'poslovanje', 'ekonomija', 'plivanje', 'statistika', 'engleski'], {'statistika': 4, 'matematika': 2, 'geografija': 3, 'ekonomija': 2, 'poslovanje': 1, 'plivanje': 3, 'engleski': 3, 'fizika': 1}, 4)

Zadatak

Devet televizijskih postaja je smješteno u devet gradova $A,$ $B,$ $C,$ $D,$ $E,$ $F,$ $G,$ $H,$ $I$ čije su međusobne udaljenosti u kilometrima dane u tablici.

  A B C D E F G H
B 85              
C 137 165            
D 123 39 205          
E 164 132 117 171        
F 105 75 235 92 201      
G 134 191 252 223 298 177    
H 114 77 113 117 54 147 247  
I 132 174 22 213 138 237 245 120

Svakoj televizijskoj postaji se treba dodijeliti kanal preko kojeg će emitirati svoj program. Zbog nesmetanog emitiranja programa, televizijskim postajama koje su na udaljenosti manjoj od 150 km treba dodijeliti različite kanale. Televizijske postaje koje su na udaljenosti većoj od 150 km mogu nesmetano emitirati svoje programe preko istog kanala.

  • Koliko je najmanje kanala potrebno kako bi sve televizijske postaje mogle nesmetano emitirati svoje programe? Problem modelirajte pomoću grafova. Opišite kratko i jasno svoj postupak modeliranja i sve svoje tvrdnje precizno obrazložite.

  • U grafu kojeg ste dobili u prethodnom dijelu zadatka pronađite jednu najveću kliku i ispitajte da li je taj graf planarni. Sve svoje tvrdnje precizno obrazložite.

Rješenje

Konstruiramo graf u kojemu će vrhovi biti televizijske postaje, a dvije televizijske postaje su spojene bridom ako i samo ako su na udaljenosti manjoj od 150 km. Tada je minimalni broj kanala jednak kromatskom broju konstruiranog grafa.

In [56]:
G2=Graph({"A":["B","C","D","F","G","H","I"],"B":["D","E","F","H"],"C":["E","H","I"], 
          "D":["F","H"],"E":["H","I"],"F":["H"],"H":["I"]})
In [57]:
G2.show(layout="circular",figsize=(4,4))

Kromatski broj grafa je 5 pa je potrebno minimalno 5 različitih kanala.

In [58]:
G2.chromatic_number()
Out[58]:
5

Jedno bojanje vrhova s minimalnim brojem boja. U istom elementu particije vrhova su one televizijske postaje koje mogu emitirati svoje programe na istom kanalu, a to su zapravo one postaje kojima je dodijeljena ista boja.

In [59]:
G2.coloring()
Out[59]:
[['F'], ['D', 'I'], ['H'], ['A', 'E'], ['B', 'C', 'G']]

želimo li to prikazati vizualno na samom grafu

In [60]:
boje2=G2.coloring(hex_colors=True);boje2
Out[60]:
{'#0066ff': ['F'],
 '#00ff66': ['D', 'I'],
 '#cbff00': ['B', 'C', 'G'],
 '#cc00ff': ['H'],
 '#ff0000': ['A', 'E']}
In [61]:
G2.show(layout="circular",figsize=(4,4),vertex_color=boje2)

U grafu postoji jedinstvena najveća klika reda 5 i to je klika {A, B, D, F, H}.

In [62]:
G2.clique_number()
Out[62]:
5
In [63]:
G2.clique_maximum()
Out[63]:
['A', 'B', 'D', 'F', 'H']
In [64]:
G2.cliques_maximum()
Out[64]:
[['A', 'B', 'D', 'F', 'H']]

Promatrani graf nije planarni jer sadrži podgraf $K_5$ koji nije planarni.

In [65]:
G2.is_planar()
Out[65]:
False

Pogledajmo kako još pohlepna bojanja rade na promatranom grafu. Pokrenite implementirane algoritme za pohlepno bojanje na zadanom grafu 10 000 puta i obratite pažnju da li uvijek daju bojanje vrhova s minimalnim brojem boja.

In [66]:
for k in xrange(30):
    print random_bojanje(G2)

(['A', 'D', 'F', 'I', 'C', 'E', 'B', 'G', 'H'], {'A': 1, 'C': 3, 'B': 4, 'E': 1, 'D': 2, 'G': 2, 'F': 3, 'I': 2, 'H': 5}, 5)
(['G', 'I', 'A', 'C', 'E', 'D', 'H', 'B', 'F'], {'A': 2, 'C': 3, 'B': 3, 'E': 2, 'D': 1, 'G': 1, 'F': 5, 'I': 1, 'H': 4}, 5)
(['G', 'F', 'H', 'D', 'I', 'B', 'E', 'A', 'C'], {'A': 5, 'C': 4, 'B': 4, 'E': 3, 'D': 3, 'G': 1, 'F': 1, 'I': 1, 'H': 2}, 5)
(['B', 'D', 'A', 'G', 'F', 'E', 'H', 'C', 'I'], {'A': 3, 'C': 1, 'B': 1, 'E': 2, 'D': 2, 'G': 1, 'F': 4, 'I': 4, 'H': 5}, 5)
(['D', 'F', 'G', 'A', 'B', 'H', 'C', 'E', 'I'], {'A': 3, 'C': 1, 'B': 4, 'E': 2, 'D': 1, 'G': 1, 'F': 2, 'I': 4, 'H': 5}, 5)
(['D', 'G', 'C', 'I', 'F', 'B', 'A', 'H', 'E'], {'A': 4, 'C': 1, 'B': 3, 'E': 4, 'D': 1, 'G': 1, 'F': 2, 'I': 2, 'H': 5}, 5)
(['A', 'D', 'B', 'G', 'E', 'F', 'H', 'I', 'C'], {'A': 1, 'C': 3, 'B': 3, 'E': 1, 'D': 2, 'G': 2, 'F': 4, 'I': 2, 'H': 5}, 5)
(['I', 'B', 'G', 'A', 'C', 'E', 'H', 'D', 'F'], {'A': 2, 'C': 3, 'B': 1, 'E': 2, 'D': 3, 'G': 1, 'F': 5, 'I': 1, 'H': 4}, 5)
(['D', 'G', 'B', 'F', 'A', 'I', 'C', 'H', 'E'], {'A': 4, 'C': 2, 'B': 2, 'E': 3, 'D': 1, 'G': 1, 'F': 3, 'I': 1, 'H': 5}, 5)
(['D', 'I', 'A', 'F', 'G', 'B', 'E', 'C', 'H'], {'A': 2, 'C': 3, 'B': 4, 'E': 2, 'D': 1, 'G': 1, 'F': 3, 'I': 1, 'H': 5}, 5)
(['F', 'A', 'E', 'D', 'C', 'I', 'G', 'B', 'H'], {'A': 2, 'C': 3, 'B': 4, 'E': 1, 'D': 3, 'G': 1, 'F': 1, 'I': 4, 'H': 5}, 5)
(['B', 'D', 'C', 'G', 'H', 'F', 'E', 'A', 'I'], {'A': 5, 'C': 1, 'B': 1, 'E': 2, 'D': 2, 'G': 1, 'F': 4, 'I': 4, 'H': 3}, 5)
(['C', 'B', 'A', 'H', 'G', 'F', 'I', 'D', 'E'], {'A': 2, 'C': 1, 'B': 1, 'E': 2, 'D': 5, 'G': 1, 'F': 4, 'I': 4, 'H': 3}, 5)
(['I', 'G', 'F', 'D', 'C', 'A', 'E', 'B', 'H'], {'A': 3, 'C': 2, 'B': 4, 'E': 3, 'D': 2, 'G': 1, 'F': 1, 'I': 1, 'H': 5}, 5)
(['G', 'F', 'A', 'H', 'C', 'B', 'D', 'E', 'I'], {'A': 2, 'C': 1, 'B': 4, 'E': 2, 'D': 5, 'G': 1, 'F': 1, 'I': 4, 'H': 3}, 5)
(['I', 'E', 'C', 'H', 'B', 'F', 'A', 'D', 'G'], {'A': 5, 'C': 3, 'B': 1, 'E': 2, 'D': 3, 'G': 1, 'F': 2, 'I': 1, 'H': 4}, 5)
(['I', 'H', 'E', 'F', 'A', 'C', 'G', 'B', 'D'], {'A': 3, 'C': 4, 'B': 4, 'E': 3, 'D': 5, 'G': 1, 'F': 1, 'I': 1, 'H': 2}, 5)
(['C', 'D', 'I', 'E', 'A', 'F', 'H', 'G', 'B'], {'A': 3, 'C': 1, 'B': 5, 'E': 3, 'D': 1, 'G': 1, 'F': 2, 'I': 2, 'H': 4}, 5)
(['C', 'H', 'I', 'B', 'E', 'A', 'D', 'G', 'F'], {'A': 4, 'C': 1, 'B': 1, 'E': 4, 'D': 3, 'G': 1, 'F': 5, 'I': 3, 'H': 2}, 5)
(['F', 'G', 'D', 'E', 'C', 'A', 'I', 'B', 'H'], {'A': 3, 'C': 2, 'B': 4, 'E': 1, 'D': 2, 'G': 1, 'F': 1, 'I': 4, 'H': 5}, 5)
(['H', 'E', 'A', 'F', 'G', 'C', 'D', 'B', 'I'], {'A': 2, 'C': 3, 'B': 5, 'E': 2, 'D': 4, 'G': 1, 'F': 3, 'I': 4, 'H': 1}, 5)
(['A', 'G', 'I', 'D', 'E', 'H', 'B', 'C', 'F'], {'A': 1, 'C': 4, 'B': 4, 'E': 1, 'D': 2, 'G': 2, 'F': 5, 'I': 2, 'H': 3}, 5)
(['D', 'B', 'G', 'F', 'C', 'H', 'E', 'A', 'I'], {'A': 5, 'C': 1, 'B': 2, 'E': 3, 'D': 1, 'G': 1, 'F': 3, 'I': 2, 'H': 4}, 5)
(['E', 'A', 'C', 'F', 'I', 'G', 'D', 'B', 'H'], {'A': 1, 'C': 2, 'B': 4, 'E': 1, 'D': 3, 'G': 2, 'F': 2, 'I': 3, 'H': 5}, 5)
(['G', 'I', 'D', 'F', 'A', 'H', 'B', 'C', 'E'], {'A': 3, 'C': 2, 'B': 5, 'E': 3, 'D': 1, 'G': 1, 'F': 2, 'I': 1, 'H': 4}, 5)
(['D', 'A', 'F', 'I', 'E', 'G', 'H', 'B', 'C'], {'A': 2, 'C': 3, 'B': 5, 'E': 2, 'D': 1, 'G': 1, 'F': 3, 'I': 1, 'H': 4}, 5)
(['H', 'B', 'G', 'C', 'I', 'F', 'A', 'E', 'D'], {'A': 4, 'C': 2, 'B': 2, 'E': 4, 'D': 5, 'G': 1, 'F': 3, 'I': 3, 'H': 1}, 5)
(['D', 'G', 'A', 'C', 'B', 'H', 'I', 'F', 'E'], {'A': 2, 'C': 1, 'B': 3, 'E': 2, 'D': 1, 'G': 1, 'F': 5, 'I': 3, 'H': 4}, 5)
(['D', 'C', 'E', 'A', 'I', 'B', 'F', 'G', 'H'], {'A': 2, 'C': 1, 'B': 3, 'E': 2, 'D': 1, 'G': 1, 'F': 4, 'I': 3, 'H': 5}, 5)
(['G', 'I', 'A', 'F', 'B', 'C', 'D', 'E', 'H'], {'A': 2, 'C': 3, 'B': 3, 'E': 2, 'D': 4, 'G': 1, 'F': 1, 'I': 1, 'H': 5}, 5)
In [67]:
for k in xrange(10):
    print Welsh_Powell(G2)

(['H', 'A', 'B', 'E', 'C', 'I', 'D', 'F', 'G'], {'A': 2, 'C': 3, 'B': 3, 'E': 2, 'D': 4, 'G': 1, 'F': 5, 'I': 4, 'H': 1}, 5)
(['H', 'A', 'B', 'E', 'D', 'I', 'F', 'C', 'G'], {'A': 2, 'C': 4, 'B': 3, 'E': 2, 'D': 4, 'G': 1, 'F': 5, 'I': 3, 'H': 1}, 5)
(['A', 'H', 'B', 'C', 'F', 'E', 'I', 'D', 'G'], {'A': 1, 'C': 3, 'B': 3, 'E': 1, 'D': 5, 'G': 2, 'F': 4, 'I': 4, 'H': 2}, 5)
(['H', 'A', 'B', 'D', 'I', 'E', 'F', 'C', 'G'], {'A': 2, 'C': 4, 'B': 3, 'E': 2, 'D': 4, 'G': 1, 'F': 5, 'I': 3, 'H': 1}, 5)
(['A', 'H', 'B', 'E', 'D', 'I', 'F', 'C', 'G'], {'A': 1, 'C': 4, 'B': 3, 'E': 1, 'D': 4, 'G': 2, 'F': 5, 'I': 3, 'H': 2}, 5)
(['H', 'A', 'B', 'F', 'I', 'D', 'E', 'C', 'G'], {'A': 2, 'C': 4, 'B': 3, 'E': 2, 'D': 5, 'G': 1, 'F': 4, 'I': 3, 'H': 1}, 5)
(['A', 'H', 'B', 'C', 'I', 'F', 'D', 'E', 'G'], {'A': 1, 'C': 3, 'B': 3, 'E': 1, 'D': 5, 'G': 2, 'F': 4, 'I': 4, 'H': 2}, 5)
(['A', 'H', 'B', 'E', 'D', 'I', 'F', 'C', 'G'], {'A': 1, 'C': 4, 'B': 3, 'E': 1, 'D': 4, 'G': 2, 'F': 5, 'I': 3, 'H': 2}, 5)
(['H', 'A', 'B', 'C', 'F', 'I', 'D', 'E', 'G'], {'A': 2, 'C': 3, 'B': 3, 'E': 2, 'D': 5, 'G': 1, 'F': 4, 'I': 4, 'H': 1}, 5)
(['A', 'H', 'B', 'F', 'D', 'C', 'E', 'I', 'G'], {'A': 1, 'C': 3, 'B': 3, 'E': 1, 'D': 5, 'G': 2, 'F': 4, 'I': 4, 'H': 2}, 5)
In [68]:
for k in xrange(10):
    print Brelaz(G2)

(['A', 'H', 'C', 'I', 'E', 'F', 'D', 'B', 'G'], {'A': 1, 'C': 3, 'B': 5, 'E': 1, 'D': 4, 'G': 2, 'F': 3, 'I': 4, 'H': 2}, 5)
(['A', 'H', 'B', 'F', 'D', 'E', 'I', 'C', 'G'], {'A': 1, 'C': 4, 'B': 3, 'E': 1, 'D': 5, 'G': 2, 'F': 4, 'I': 3, 'H': 2}, 5)
(['H', 'F', 'D', 'A', 'B', 'C', 'I', 'E', 'G'], {'A': 4, 'C': 2, 'B': 5, 'E': 4, 'D': 3, 'G': 1, 'F': 2, 'I': 3, 'H': 1}, 5)
(['A', 'H', 'F', 'B', 'D', 'I', 'E', 'C', 'G'], {'A': 1, 'C': 4, 'B': 4, 'E': 1, 'D': 5, 'G': 2, 'F': 3, 'I': 3, 'H': 2}, 5)
(['H', 'F', 'A', 'B', 'D', 'C', 'I', 'E', 'G'], {'A': 3, 'C': 2, 'B': 4, 'E': 3, 'D': 5, 'G': 1, 'F': 2, 'I': 4, 'H': 1}, 5)
(['H', 'A', 'F', 'B', 'D', 'E', 'C', 'I', 'G'], {'A': 2, 'C': 3, 'B': 4, 'E': 2, 'D': 5, 'G': 1, 'F': 3, 'I': 4, 'H': 1}, 5)
(['H', 'A', 'D', 'B', 'F', 'C', 'I', 'E', 'G'], {'A': 2, 'C': 3, 'B': 4, 'E': 2, 'D': 3, 'G': 1, 'F': 5, 'I': 4, 'H': 1}, 5)
(['H', 'F', 'D', 'B', 'A', 'I', 'C', 'E', 'G'], {'A': 5, 'C': 3, 'B': 4, 'E': 5, 'D': 3, 'G': 1, 'F': 2, 'I': 2, 'H': 1}, 5)
(['H', 'C', 'E', 'I', 'A', 'F', 'D', 'B', 'G'], {'A': 3, 'C': 2, 'B': 5, 'E': 3, 'D': 4, 'G': 1, 'F': 2, 'I': 4, 'H': 1}, 5)
(['A', 'F', 'B', 'D', 'H', 'E', 'C', 'I', 'G'], {'A': 1, 'C': 2, 'B': 3, 'E': 1, 'D': 4, 'G': 2, 'F': 2, 'I': 3, 'H': 5}, 5)

Zadatak

Pokažite da Brelazov i Welsh-Powellov algoritam ne daju uvijek bojanje vrhova s minimalnim brojem boja u grafu

Rješenje

In [69]:
G3=Graph({"v1":["v2","v5","v9"],"v2":["v3","v8"],"v3":["v4","v7"],"v4":["v6","v9"],
          "v5":["v6","v7"],"v6":["v8"],"v7":["v8","v9"],"v8":["v9"]})

Kromatski broj zadanog grafa je 3.

In [70]:
G3.chromatic_number()
Out[70]:
3

Vidimo da nam se dogodilo da u 20 izvođenja Brelazov i Welsh-Powellov algoritam nisu uvijek dali bojanje vrhova s minimalnim brojem boja (ukoliko se to ne dogodi u prvih 20 puta, ponovite algoritme više od 20 puta).

In [71]:
for k in xrange(20):
    print Brelaz(G3)

(['v7', 'v3', 'v2', 'v4', 'v9', 'v8', 'v6', 'v5', 'v1'], {'v1': 4, 'v2': 1, 'v3': 2, 'v4': 1, 'v5': 3, 'v6': 2, 'v7': 1, 'v8': 3, 'v9': 2}, 4)
(['v8', 'v9', 'v7', 'v1', 'v5', 'v6', 'v4', 'v3', 'v2'], {'v1': 1, 'v2': 3, 'v3': 2, 'v4': 1, 'v5': 2, 'v6': 3, 'v7': 3, 'v8': 1, 'v9': 2}, 3)
(['v8', 'v9', 'v7', 'v4', 'v3', 'v2', 'v1', 'v5', 'v6'], {'v1': 1, 'v2': 3, 'v3': 2, 'v4': 1, 'v5': 2, 'v6': 3, 'v7': 3, 'v8': 1, 'v9': 2}, 3)
(['v8', 'v2', 'v6', 'v5', 'v1', 'v9', 'v7', 'v3', 'v4'], {'v1': 3, 'v2': 2, 'v3': 1, 'v4': 3, 'v5': 1, 'v6': 2, 'v7': 3, 'v8': 1, 'v9': 2}, 3)
(['v8', 'v7', 'v9', 'v1', 'v5', 'v6', 'v4', 'v3', 'v2'], {'v1': 1, 'v2': 2, 'v3': 3, 'v4': 1, 'v5': 3, 'v6': 2, 'v7': 2, 'v8': 1, 'v9': 3}, 3)
(['v8', 'v9', 'v7', 'v2', 'v3', 'v4', 'v6', 'v5', 'v1'], {'v1': 3, 'v2': 2, 'v3': 1, 'v4': 3, 'v5': 1, 'v6': 2, 'v7': 3, 'v8': 1, 'v9': 2}, 3)
(['v7', 'v3', 'v5', 'v2', 'v1', 'v9', 'v8', 'v6', 'v4'], {'v1': 3, 'v2': 1, 'v3': 2, 'v4': 3, 'v5': 2, 'v6': 1, 'v7': 1, 'v8': 3, 'v9': 2}, 3)
(['v8', 'v7', 'v9', 'v2', 'v1', 'v5', 'v6', 'v4', 'v3'], {'v1': 1, 'v2': 2, 'v3': 3, 'v4': 1, 'v5': 3, 'v6': 2, 'v7': 2, 'v8': 1, 'v9': 3}, 3)
(['v7', 'v9', 'v8', 'v5', 'v6', 'v4', 'v3', 'v2', 'v1'], {'v1': 3, 'v2': 1, 'v3': 2, 'v4': 3, 'v5': 2, 'v6': 1, 'v7': 1, 'v8': 3, 'v9': 2}, 3)
(['v9', 'v7', 'v8', 'v6', 'v5', 'v1', 'v2', 'v3', 'v4'], {'v1': 2, 'v2': 1, 'v3': 3, 'v4': 2, 'v5': 3, 'v6': 1, 'v7': 2, 'v8': 3, 'v9': 1}, 3)
(['v7', 'v9', 'v8', 'v2', 'v1', 'v5', 'v6', 'v4', 'v3'], {'v1': 3, 'v2': 1, 'v3': 2, 'v4': 3, 'v5': 2, 'v6': 1, 'v7': 1, 'v8': 3, 'v9': 2}, 3)
(['v8', 'v2', 'v3', 'v4', 'v9', 'v1', 'v6', 'v7', 'v5'], {'v1': 1, 'v2': 2, 'v3': 1, 'v4': 2, 'v5': 4, 'v6': 3, 'v7': 2, 'v8': 1, 'v9': 3}, 4)
(['v7', 'v8', 'v9', 'v5', 'v1', 'v2', 'v3', 'v4', 'v6'], {'v1': 1, 'v2': 3, 'v3': 2, 'v4': 1, 'v5': 2, 'v6': 3, 'v7': 1, 'v8': 2, 'v9': 3}, 3)
(['v8', 'v2', 'v1', 'v9', 'v7', 'v5', 'v6', 'v3', 'v4'], {'v1': 1, 'v2': 2, 'v3': 1, 'v4': 4, 'v5': 2, 'v6': 3, 'v7': 3, 'v8': 1, 'v9': 2}, 4)
(['v7', 'v5', 'v6', 'v3', 'v4', 'v9', 'v8', 'v2', 'v1'], {'v1': 3, 'v2': 1, 'v3': 2, 'v4': 3, 'v5': 2, 'v6': 1, 'v7': 1, 'v8': 3, 'v9': 2}, 3)
(['v9', 'v4', 'v1', 'v6', 'v5', 'v7', 'v8', 'v2', 'v3'], {'v1': 2, 'v2': 1, 'v3': 3, 'v4': 2, 'v5': 3, 'v6': 1, 'v7': 2, 'v8': 3, 'v9': 1}, 3)
(['v9', 'v8', 'v7', 'v1', 'v5', 'v6', 'v4', 'v3', 'v2'], {'v1': 2, 'v2': 3, 'v3': 1, 'v4': 2, 'v5': 1, 'v6': 3, 'v7': 3, 'v8': 2, 'v9': 1}, 3)
(['v9', 'v7', 'v8', 'v5', 'v6', 'v4', 'v3', 'v2', 'v1'], {'v1': 3, 'v2': 2, 'v3': 1, 'v4': 3, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 3, 'v9': 1}, 3)
(['v7', 'v8', 'v9', 'v5', 'v1', 'v2', 'v3', 'v4', 'v6'], {'v1': 1, 'v2': 3, 'v3': 2, 'v4': 1, 'v5': 2, 'v6': 3, 'v7': 1, 'v8': 2, 'v9': 3}, 3)
(['v9', 'v7', 'v8', 'v2', 'v3', 'v4', 'v6', 'v5', 'v1'], {'v1': 2, 'v2': 1, 'v3': 3, 'v4': 2, 'v5': 3, 'v6': 1, 'v7': 2, 'v8': 3, 'v9': 1}, 3)
In [72]:
for k in xrange(20):
    print Welsh_Powell(G3)

(['v8', 'v7', 'v9', 'v5', 'v4', 'v6', 'v3', 'v1', 'v2'], {'v1': 2, 'v2': 4, 'v3': 3, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 1, 'v9': 3}, 4)
(['v7', 'v9', 'v8', 'v5', 'v3', 'v6', 'v4', 'v1', 'v2'], {'v1': 1, 'v2': 4, 'v3': 2, 'v4': 3, 'v5': 2, 'v6': 1, 'v7': 1, 'v8': 3, 'v9': 2}, 4)
(['v7', 'v8', 'v9', 'v3', 'v2', 'v6', 'v4', 'v5', 'v1'], {'v1': 4, 'v2': 1, 'v3': 2, 'v4': 4, 'v5': 2, 'v6': 1, 'v7': 1, 'v8': 2, 'v9': 3}, 4)
(['v7', 'v9', 'v8', 'v1', 'v3', 'v5', 'v4', 'v2', 'v6'], {'v1': 1, 'v2': 4, 'v3': 2, 'v4': 1, 'v5': 2, 'v6': 4, 'v7': 1, 'v8': 3, 'v9': 2}, 4)
(['v9', 'v8', 'v7', 'v3', 'v5', 'v4', 'v2', 'v6', 'v1'], {'v1': 2, 'v2': 3, 'v3': 1, 'v4': 2, 'v5': 1, 'v6': 3, 'v7': 3, 'v8': 2, 'v9': 1}, 3)
(['v9', 'v8', 'v7', 'v4', 'v5', 'v1', 'v3', 'v6', 'v2'], {'v1': 2, 'v2': 3, 'v3': 1, 'v4': 2, 'v5': 1, 'v6': 3, 'v7': 3, 'v8': 2, 'v9': 1}, 3)
(['v7', 'v8', 'v9', 'v6', 'v4', 'v2', 'v1', 'v3', 'v5'], {'v1': 2, 'v2': 1, 'v3': 3, 'v4': 2, 'v5': 3, 'v6': 1, 'v7': 1, 'v8': 2, 'v9': 3}, 3)
(['v7', 'v9', 'v8', 'v3', 'v4', 'v6', 'v5', 'v1', 'v2'], {'v1': 1, 'v2': 4, 'v3': 2, 'v4': 1, 'v5': 3, 'v6': 2, 'v7': 1, 'v8': 3, 'v9': 2}, 4)
(['v8', 'v7', 'v9', 'v6', 'v4', 'v3', 'v1', 'v5', 'v2'], {'v1': 1, 'v2': 2, 'v3': 3, 'v4': 1, 'v5': 3, 'v6': 2, 'v7': 2, 'v8': 1, 'v9': 3}, 3)
(['v8', 'v9', 'v7', 'v5', 'v6', 'v2', 'v1', 'v4', 'v3'], {'v1': 3, 'v2': 2, 'v3': 4, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 3, 'v8': 1, 'v9': 2}, 4)
(['v9', 'v8', 'v7', 'v1', 'v6', 'v5', 'v2', 'v4', 'v3'], {'v1': 2, 'v2': 1, 'v3': 4, 'v4': 2, 'v5': 4, 'v6': 1, 'v7': 3, 'v8': 2, 'v9': 1}, 4)
(['v8', 'v7', 'v9', 'v3', 'v5', 'v2', 'v4', 'v6', 'v1'], {'v1': 4, 'v2': 2, 'v3': 1, 'v4': 2, 'v5': 1, 'v6': 3, 'v7': 2, 'v8': 1, 'v9': 3}, 4)
(['v8', 'v9', 'v7', 'v2', 'v4', 'v1', 'v3', 'v6', 'v5'], {'v1': 1, 'v2': 2, 'v3': 4, 'v4': 1, 'v5': 4, 'v6': 2, 'v7': 3, 'v8': 1, 'v9': 2}, 4)
(['v9', 'v7', 'v8', 'v3', 'v1', 'v2', 'v5', 'v4', 'v6'], {'v1': 2, 'v2': 4, 'v3': 1, 'v4': 2, 'v5': 1, 'v6': 4, 'v7': 2, 'v8': 3, 'v9': 1}, 4)
(['v7', 'v8', 'v9', 'v4', 'v3', 'v2', 'v5', 'v6', 'v1'], {'v1': 4, 'v2': 1, 'v3': 2, 'v4': 1, 'v5': 2, 'v6': 3, 'v7': 1, 'v8': 2, 'v9': 3}, 4)
(['v9', 'v8', 'v7', 'v5', 'v6', 'v4', 'v1', 'v2', 'v3'], {'v1': 2, 'v2': 1, 'v3': 4, 'v4': 2, 'v5': 1, 'v6': 3, 'v7': 3, 'v8': 2, 'v9': 1}, 4)
(['v8', 'v9', 'v7', 'v2', 'v4', 'v5', 'v3', 'v1', 'v6'], {'v1': 3, 'v2': 2, 'v3': 4, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 3, 'v8': 1, 'v9': 2}, 4)
(['v7', 'v9', 'v8', 'v5', 'v3', 'v2', 'v1', 'v4', 'v6'], {'v1': 3, 'v2': 1, 'v3': 2, 'v4': 1, 'v5': 2, 'v6': 4, 'v7': 1, 'v8': 3, 'v9': 2}, 4)
(['v7', 'v9', 'v8', 'v6', 'v3', 'v4', 'v2', 'v1', 'v5'], {'v1': 3, 'v2': 1, 'v3': 2, 'v4': 3, 'v5': 2, 'v6': 1, 'v7': 1, 'v8': 3, 'v9': 2}, 3)
(['v9', 'v7', 'v8', 'v5', 'v2', 'v3', 'v6', 'v4', 'v1'], {'v1': 2, 'v2': 1, 'v3': 3, 'v4': 4, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 3, 'v9': 1}, 4)

Bojanje bridova grafa

In [73]:
from sage.graphs.graph_coloring import edge_coloring

Zadatak

Odredite kromatski i bridno kromatski broj grafa

Rješenje

In [74]:
G4=Graph({1:[2,4,5,6],2:[3,5,7],3:[4,5,6,7],4:[5,6,7]}) 
G4poz={1:[0,0],2:[3,0],3:[3,3],4:[0,3],5:[1.5,1.5],6:[-1,4],7:[4,4]}
In [75]:
G4.show(pos=G4poz)

Kromatski broj grafa je 3.

In [76]:
G4.chromatic_number()
Out[76]:
3

Jedno bojanje vrhova s minimalnim brojem boja

In [77]:
G4.coloring()
Out[77]:
[[2, 4], [1, 3], [5, 6, 7]]
In [78]:
G4.show(pos=G4poz,vertex_color=G4.coloring(hex_colors=True))

Pogledajmo kako se ponašaju pohlepna bojanja na ovom grafu. Izvršite svaki od tih algoritama 10 000 puta na zadanom grafu i donesite neki zaključak na temelju tog eksperimenta.

In [79]:
for k in xrange(20):
    print random_bojanje(G4)

([4, 7, 5, 1, 6, 2, 3], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([2, 6, 4, 3, 7, 1, 5], {1: 3, 2: 1, 3: 3, 4: 2, 5: 4, 6: 1, 7: 4}, 4)
([7, 6, 4, 1, 5, 2, 3], {1: 3, 2: 2, 3: 3, 4: 2, 5: 1, 6: 1, 7: 1}, 3)
([4, 2, 6, 1, 3, 5, 7], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([4, 7, 6, 1, 3, 5, 2], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([2, 3, 6, 1, 4, 7, 5], {1: 2, 2: 1, 3: 2, 4: 3, 5: 4, 6: 1, 7: 4}, 4)
([1, 7, 3, 6, 2, 4, 5], {1: 1, 2: 3, 3: 2, 4: 4, 5: 5, 6: 3, 7: 1}, 5)
([4, 6, 1, 7, 2, 5, 3], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([6, 2, 3, 7, 1, 4, 5], {1: 2, 2: 1, 3: 2, 4: 4, 5: 3, 6: 1, 7: 3}, 4)
([4, 2, 5, 7, 3, 6, 1], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([2, 3, 1, 4, 6, 5, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([6, 3, 4, 2, 5, 1, 7], {1: 2, 2: 1, 3: 2, 4: 3, 5: 4, 6: 1, 7: 4}, 4)
([6, 2, 5, 4, 7, 1, 3], {1: 4, 2: 1, 3: 4, 4: 3, 5: 2, 6: 1, 7: 2}, 4)
([4, 1, 7, 5, 2, 6, 3], {1: 2, 2: 1, 3: 4, 4: 1, 5: 3, 6: 3, 7: 2}, 4)
([2, 7, 3, 1, 6, 5, 4], {1: 2, 2: 1, 3: 3, 4: 5, 5: 4, 6: 1, 7: 2}, 5)
([1, 7, 4, 5, 2, 3, 6], {1: 1, 2: 2, 3: 4, 4: 2, 5: 3, 6: 3, 7: 1}, 4)
([4, 1, 2, 6, 3, 7, 5], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([7, 2, 4, 5, 6, 1, 3], {1: 3, 2: 2, 3: 3, 4: 2, 5: 1, 6: 1, 7: 1}, 3)
([2, 7, 4, 6, 3, 5, 1], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([3, 5, 4, 1, 2, 7, 6], {1: 1, 2: 3, 3: 1, 4: 3, 5: 2, 6: 2, 7: 2}, 3)
In [80]:
for k in xrange(20):
    print Welsh_Powell(G4)

([4, 3, 1, 5, 2, 6, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 1, 2, 5, 6, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 2, 1, 5, 7, 6], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 5, 1, 2, 6, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 1, 2, 5, 6, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 5, 2, 1, 7, 6], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 2, 1, 5, 6, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 2, 5, 1, 7, 6], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 5, 2, 1, 6, 7], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 5, 1, 2, 6, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 5, 1, 2, 6, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 2, 5, 1, 6, 7], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 5, 2, 1, 7, 6], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 5, 2, 1, 7, 6], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 1, 2, 5, 7, 6], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 2, 1, 5, 6, 7], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 5, 1, 2, 7, 6], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 2, 5, 1, 7, 6], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 5, 1, 2, 6, 7], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 2, 1, 5, 6, 7], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
In [81]:
for k in xrange(20):
    print Brelaz(G4)

([4, 5, 1, 6, 2, 3, 7], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([3, 4, 5, 6, 7, 1, 2], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([4, 5, 1, 3, 6, 2, 7], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([3, 4, 7, 2, 5, 6, 1], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([4, 1, 5, 6, 3, 2, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([4, 3, 7, 5, 2, 6, 1], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([4, 6, 3, 1, 5, 2, 7], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([4, 6, 1, 3, 5, 7, 2], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([3, 7, 2, 5, 4, 6, 1], {1: 1, 2: 3, 3: 1, 4: 3, 5: 2, 6: 2, 7: 2}, 3)
([3, 7, 4, 5, 2, 1, 6], {1: 1, 2: 3, 3: 1, 4: 3, 5: 2, 6: 2, 7: 2}, 3)
([3, 2, 7, 5, 1, 4, 6], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 4, 7, 6, 2, 1, 5], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([4, 6, 1, 3, 7, 5, 2], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)
([3, 2, 5, 1, 4, 7, 6], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 6, 4, 1, 7, 5, 2], {1: 1, 2: 3, 3: 1, 4: 3, 5: 2, 6: 2, 7: 2}, 3)
([3, 4, 6, 1, 7, 5, 2], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([4, 1, 6, 5, 2, 3, 7], {1: 2, 2: 1, 3: 2, 4: 1, 5: 3, 6: 3, 7: 3}, 3)
([3, 2, 7, 5, 4, 6, 1], {1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 3, 7: 3}, 3)
([3, 6, 4, 7, 5, 1, 2], {1: 1, 2: 3, 3: 1, 4: 3, 5: 2, 6: 2, 7: 2}, 3)
([4, 5, 1, 3, 2, 6, 7], {1: 3, 2: 1, 3: 3, 4: 1, 5: 2, 6: 2, 7: 2}, 3)

Bridno kromatski broj grafa je 5.

In [82]:
edge_coloring(G4,value_only=True)
Out[82]:
5

Jedno bojanje bridova s minimalnim brojem boja. Bridovima iz istog elementa particije bridova je pridružena ista boja.

In [83]:
edge_coloring(G4)
Out[83]:
[[(1, 4), (2, 7), (3, 5)],
 [(1, 2), (3, 4)],
 [(1, 6), (2, 3), (4, 5)],
 [(1, 5), (3, 7), (4, 6)],
 [(2, 5), (3, 6), (4, 7)]]

Vizualizacija obojenih bridova na slici

In [84]:
boje_bridova=edge_coloring(G4,hex_colors=True);boje_bridova
Out[84]:
{'#0066ff': [(1, 5), (3, 7), (4, 6)],
 '#00ff66': [(1, 6), (2, 3), (4, 5)],
 '#cbff00': [(1, 2), (3, 4)],
 '#cc00ff': [(2, 5), (3, 6), (4, 7)],
 '#ff0000': [(1, 4), (2, 7), (3, 5)]}
In [85]:
G4.show(pos=G4poz,edge_colors=boje_bridova)

Implementirane algoritme za pohlepno bojanje vrhova grafa možemo primijeniti i za pohlepno bojanje bridova grafa. Ukoliko želimo pronaći neko pohlepno bojanje bridova grafa $G$, tada naše implementirane algoritme moramo primijeniti na linijskom grafu grafa $G$, tj. na grafu $L(G)$. Jasno, pohlepno bojanje bridova grafa općenito ne daje bojanje bridova s minimalnim brojem boja.

In [86]:
G4line=G4.line_graph(labels=False)

Ovdje je svaki od pohlepnih algoritama primijenjen samo 10 puta na promatranom grafu. Primijenite svaki od tih algoritama 10 000 puta na zadanom grafu i donesite na temelju toga neki zaključak.

In [87]:
for k in xrange(10):
    print random_bojanje(G4line)
    print

([(2, 7), (3, 6), (3, 5), (2, 3), (2, 5), (4, 7), (3, 4), (1, 6), (3, 7), (4, 5), (1, 5), (4, 6), (1, 2), (1, 4)], {(2, 7): 1, (1, 2): 5, (4, 7): 2, (4, 6): 3, (4, 5): 1, (1, 4): 6, (1, 5): 3, (2, 3): 3, (3, 6): 1, (3, 7): 5, (1, 6): 2, (2, 5): 4, (3, 4): 4, (3, 5): 2}, 6)

([(1, 5), (3, 6), (1, 2), (2, 7), (3, 7), (4, 5), (3, 4), (4, 6), (4, 7), (1, 6), (3, 5), (1, 4), (2, 3), (2, 5)], {(1, 2): 2, (2, 7): 1, (4, 7): 5, (4, 6): 4, (4, 5): 2, (1, 4): 6, (1, 5): 1, (1, 6): 3, (3, 6): 1, (2, 3): 5, (3, 7): 2, (2, 5): 3, (3, 4): 3, (3, 5): 4}, 6)

([(1, 2), (3, 6), (1, 5), (1, 4), (2, 5), (4, 6), (4, 7), (2, 3), (3, 7), (3, 4), (1, 6), (3, 5), (2, 7), (4, 5)], {(1, 2): 1, (2, 7): 4, (4, 7): 1, (4, 6): 2, (1, 6): 4, (4, 5): 6, (1, 4): 3, (1, 5): 2, (2, 3): 2, (3, 6): 1, (3, 7): 3, (2, 5): 3, (3, 4): 4, (3, 5): 5}, 6)

([(4, 6), (3, 7), (2, 7), (1, 6), (3, 4), (1, 2), (1, 5), (2, 3), (3, 5), (1, 4), (2, 5), (3, 6), (4, 5), (4, 7)], {(2, 7): 2, (1, 2): 1, (4, 7): 3, (4, 6): 1, (4, 5): 6, (1, 4): 4, (1, 5): 3, (1, 6): 2, (3, 6): 5, (2, 3): 3, (3, 7): 1, (2, 5): 5, (3, 4): 2, (3, 5): 4}, 6)

([(3, 7), (4, 5), (4, 6), (1, 4), (2, 3), (4, 7), (1, 2), (1, 6), (3, 4), (3, 5), (3, 6), (2, 7), (2, 5), (1, 5)], {(1, 2): 1, (2, 7): 3, (4, 7): 4, (4, 6): 2, (1, 6): 4, (4, 5): 1, (1, 4): 3, (1, 5): 2, (2, 3): 2, (3, 6): 6, (3, 7): 1, (2, 5): 4, (3, 4): 5, (3, 5): 3}, 6)

([(4, 5), (1, 2), (3, 5), (2, 5), (2, 3), (1, 6), (3, 7), (1, 4), (4, 6), (4, 7), (3, 6), (1, 5), (2, 7), (3, 4)], {(1, 2): 1, (2, 7): 5, (4, 7): 2, (4, 6): 4, (4, 5): 1, (1, 4): 3, (1, 5): 4, (2, 3): 4, (3, 6): 3, (3, 7): 1, (1, 6): 2, (2, 5): 3, (3, 4): 5, (3, 5): 2}, 5)

([(3, 5), (1, 4), (1, 6), (2, 5), (3, 7), (3, 4), (1, 5), (3, 6), (4, 7), (2, 7), (2, 3), (1, 2), (4, 6), (4, 5)], {(2, 7): 1, (1, 2): 4, (4, 7): 4, (4, 6): 5, (4, 5): 6, (1, 4): 1, (1, 5): 3, (1, 6): 2, (3, 6): 4, (2, 3): 5, (3, 7): 2, (2, 5): 2, (3, 4): 3, (3, 5): 1}, 6)

([(4, 5), (1, 6), (1, 5), (2, 5), (2, 3), (3, 5), (3, 7), (1, 4), (4, 7), (3, 6), (2, 7), (3, 4), (4, 6), (1, 2)], {(2, 7): 5, (1, 2): 4, (4, 7): 4, (4, 6): 2, (4, 5): 1, (1, 4): 3, (1, 5): 2, (1, 6): 1, (3, 6): 3, (3, 7): 2, (2, 3): 1, (2, 5): 3, (3, 4): 5, (3, 5): 4}, 5)

([(3, 5), (4, 5), (3, 6), (1, 5), (4, 6), (4, 7), (2, 5), (1, 6), (3, 4), (2, 7), (2, 3), (1, 4), (3, 7), (1, 2)], {(2, 7): 1, (1, 2): 2, (4, 7): 3, (4, 6): 1, (4, 5): 2, (1, 4): 5, (1, 5): 3, (1, 6): 4, (3, 6): 2, (3, 7): 5, (2, 3): 3, (2, 5): 4, (3, 4): 4, (3, 5): 1}, 5)

([(3, 7), (2, 7), (1, 4), (3, 5), (4, 7), (3, 6), (1, 2), (1, 6), (4, 6), (2, 5), (3, 4), (1, 5), (4, 5), (2, 3)], {(2, 7): 2, (1, 2): 3, (4, 7): 3, (4, 6): 4, (4, 5): 6, (1, 4): 1, (1, 5): 4, (1, 6): 2, (3, 6): 3, (2, 3): 4, (3, 7): 1, (2, 5): 1, (3, 4): 5, (3, 5): 2}, 6)
In [88]:
for k in xrange(10):
    print Welsh_Powell(G4line)
    print

([(3, 4), (1, 4), (2, 3), (4, 5), (3, 5), (4, 7), (1, 5), (2, 5), (3, 7), (4, 6), (3, 6), (1, 2), (2, 7), (1, 6)], {(1, 2): 3, (2, 7): 1, (4, 7): 4, (4, 6): 5, (1, 6): 4, (4, 5): 3, (1, 4): 2, (1, 5): 1, (2, 3): 2, (3, 6): 6, (3, 7): 3, (2, 5): 5, (3, 4): 1, (3, 5): 4}, 6)

([(3, 4), (1, 4), (4, 5), (3, 5), (2, 3), (3, 6), (4, 6), (4, 7), (3, 7), (1, 2), (2, 5), (1, 5), (1, 6), (2, 7)], {(1, 2): 1, (2, 7): 2, (4, 7): 4, (4, 6): 5, (1, 6): 3, (4, 5): 3, (1, 4): 2, (1, 5): 5, (2, 3): 3, (3, 6): 4, (3, 7): 5, (2, 5): 4, (3, 4): 1, (3, 5): 2}, 5)

([(3, 4), (2, 3), (3, 5), (1, 4), (4, 5), (3, 6), (3, 7), (1, 2), (2, 5), (1, 5), (4, 6), (4, 7), (1, 6), (2, 7)], {(1, 2): 1, (2, 7): 3, (4, 7): 6, (4, 6): 3, (1, 6): 5, (4, 5): 4, (1, 4): 2, (1, 5): 6, (2, 3): 2, (3, 6): 4, (3, 7): 5, (2, 5): 5, (3, 4): 1, (3, 5): 3}, 6)

([(3, 4), (1, 4), (4, 5), (2, 3), (3, 5), (4, 7), (2, 5), (1, 5), (3, 6), (3, 7), (1, 2), (4, 6), (2, 7), (1, 6)], {(1, 2): 3, (2, 7): 6, (4, 7): 4, (4, 6): 5, (1, 6): 1, (4, 5): 3, (1, 4): 2, (1, 5): 5, (2, 3): 2, (3, 6): 3, (3, 7): 5, (2, 5): 1, (3, 4): 1, (3, 5): 4}, 6)

([(3, 4), (3, 5), (4, 5), (1, 4), (2, 3), (1, 5), (1, 2), (3, 7), (2, 5), (4, 6), (4, 7), (3, 6), (2, 7), (1, 6)], {(1, 2): 4, (2, 7): 1, (4, 7): 5, (4, 6): 4, (1, 6): 3, (4, 5): 3, (1, 4): 2, (1, 5): 1, (2, 3): 3, (3, 6): 5, (3, 7): 4, (2, 5): 5, (3, 4): 1, (3, 5): 2}, 5)

([(3, 4), (4, 5), (3, 5), (1, 4), (2, 3), (4, 6), (4, 7), (3, 7), (1, 2), (1, 5), (2, 5), (3, 6), (1, 6), (2, 7)], {(1, 2): 1, (2, 7): 3, (4, 7): 5, (4, 6): 4, (1, 6): 2, (4, 5): 2, (1, 4): 3, (1, 5): 4, (2, 3): 2, (3, 6): 5, (3, 7): 4, (2, 5): 5, (3, 4): 1, (3, 5): 3}, 5)

([(3, 4), (1, 4), (2, 3), (4, 5), (3, 5), (3, 6), (1, 5), (1, 2), (2, 5), (3, 7), (4, 6), (4, 7), (2, 7), (1, 6)], {(1, 2): 3, (2, 7): 1, (4, 7): 6, (4, 6): 4, (1, 6): 5, (4, 5): 3, (1, 4): 2, (1, 5): 1, (2, 3): 2, (3, 6): 3, (3, 7): 5, (2, 5): 5, (3, 4): 1, (3, 5): 4}, 6)

([(3, 4), (1, 4), (3, 5), (2, 3), (4, 5), (3, 6), (4, 7), (2, 5), (4, 6), (1, 5), (3, 7), (1, 2), (2, 7), (1, 6)], {(1, 2): 5, (2, 7): 2, (4, 7): 4, (4, 6): 5, (1, 6): 1, (4, 5): 3, (1, 4): 2, (1, 5): 4, (2, 3): 3, (3, 6): 4, (3, 7): 5, (2, 5): 1, (3, 4): 1, (3, 5): 2}, 5)

([(3, 4), (4, 5), (1, 4), (3, 5), (2, 3), (4, 6), (3, 6), (1, 2), (4, 7), (2, 5), (3, 7), (1, 5), (2, 7), (1, 6)], {(1, 2): 1, (2, 7): 3, (4, 7): 5, (4, 6): 4, (1, 6): 2, (4, 5): 2, (1, 4): 3, (1, 5): 5, (2, 3): 2, (3, 6): 5, (3, 7): 4, (2, 5): 4, (3, 4): 1, (3, 5): 3}, 5)

([(3, 4), (1, 4), (4, 5), (3, 5), (2, 3), (2, 5), (3, 6), (4, 7), (1, 5), (1, 2), (3, 7), (4, 6), (1, 6), (2, 7)], {(1, 2): 5, (2, 7): 2, (4, 7): 4, (4, 6): 5, (1, 6): 1, (4, 5): 3, (1, 4): 2, (1, 5): 4, (2, 3): 3, (3, 6): 4, (3, 7): 5, (2, 5): 1, (3, 4): 1, (3, 5): 2}, 5)
In [89]:
for k in xrange(10):
    print Brelaz(G4line)
    print

([(3, 4), (3, 6), (3, 7), (3, 5), (2, 3), (4, 7), (4, 5), (2, 7), (2, 5), (1, 2), (1, 5), (4, 6), (1, 4), (1, 6)], {(2, 7): 1, (1, 2): 3, (4, 7): 2, (4, 6): 4, (1, 6): 6, (4, 5): 3, (1, 4): 5, (1, 5): 1, (2, 3): 5, (3, 6): 2, (3, 7): 3, (2, 5): 2, (3, 4): 1, (3, 5): 4}, 6)

([(3, 4), (4, 6), (3, 6), (1, 6), (3, 7), (2, 3), (3, 5), (4, 5), (1, 5), (2, 5), (1, 2), (2, 7), (4, 7), (1, 4)], {(1, 2): 3, (2, 7): 5, (4, 7): 4, (4, 6): 2, (4, 5): 3, (1, 4): 5, (1, 5): 2, (2, 3): 4, (3, 6): 3, (3, 7): 2, (1, 6): 1, (2, 5): 1, (3, 4): 1, (3, 5): 5}, 5)

([(3, 4), (3, 6), (4, 6), (4, 7), (4, 5), (1, 4), (1, 6), (3, 5), (1, 5), (3, 7), (2, 3), (2, 5), (2, 7), (1, 2)], {(2, 7): 3, (1, 2): 4, (4, 7): 2, (4, 6): 3, (4, 5): 4, (1, 4): 5, (1, 5): 2, (1, 6): 1, (3, 6): 2, (2, 3): 5, (3, 7): 4, (2, 5): 1, (3, 4): 1, (3, 5): 3}, 5)

([(3, 4), (3, 6), (2, 3), (3, 5), (3, 7), (2, 7), (2, 5), (4, 5), (1, 5), (4, 6), (4, 7), (1, 4), (1, 6), (1, 2)], {(2, 7): 1, (1, 2): 4, (4, 7): 2, (4, 6): 4, (1, 6): 3, (4, 5): 3, (1, 4): 5, (1, 5): 1, (2, 3): 3, (3, 6): 2, (3, 7): 5, (2, 5): 2, (3, 4): 1, (3, 5): 4}, 5)

([(3, 4), (3, 7), (3, 6), (2, 3), (3, 5), (2, 5), (2, 7), (1, 2), (1, 5), (1, 4), (4, 5), (4, 7), (4, 6), (1, 6)], {(2, 7): 3, (1, 2): 2, (4, 7): 5, (4, 6): 6, (1, 6): 1, (4, 5): 2, (1, 4): 4, (1, 5): 3, (2, 3): 4, (3, 6): 3, (3, 7): 2, (2, 5): 1, (3, 4): 1, (3, 5): 5}, 6)

([(3, 4), (4, 7), (1, 4), (4, 6), (4, 5), (3, 5), (3, 6), (3, 7), (2, 3), (2, 7), (1, 2), (1, 5), (1, 6), (2, 5)], {(2, 7): 1, (1, 2): 2, (4, 7): 2, (4, 6): 4, (1, 6): 5, (4, 5): 5, (1, 4): 3, (1, 5): 1, (2, 3): 5, (3, 6): 3, (3, 7): 4, (2, 5): 3, (3, 4): 1, (3, 5): 2}, 5)

([(3, 4), (2, 3), (3, 6), (3, 7), (3, 5), (4, 5), (4, 6), (4, 7), (1, 4), (2, 7), (1, 2), (2, 5), (1, 5), (1, 6)], {(2, 7): 1, (1, 2): 3, (4, 7): 3, (4, 6): 4, (1, 6): 2, (4, 5): 2, (1, 4): 5, (1, 5): 1, (2, 3): 2, (3, 6): 3, (3, 7): 4, (2, 5): 4, (3, 4): 1, (3, 5): 5}, 5)

([(3, 4), (1, 4), (4, 6), (4, 5), (4, 7), (3, 6), (3, 7), (3, 5), (2, 3), (1, 5), (1, 6), (2, 5), (2, 7), (1, 2)], {(2, 7): 1, (1, 2): 3, (4, 7): 5, (4, 6): 3, (1, 6): 4, (4, 5): 4, (1, 4): 2, (1, 5): 1, (2, 3): 4, (3, 6): 2, (3, 7): 3, (2, 5): 2, (3, 4): 1, (3, 5): 5}, 5)

([(3, 4), (1, 4), (4, 5), (4, 6), (4, 7), (3, 5), (3, 7), (3, 6), (2, 3), (2, 7), (2, 5), (1, 2), (1, 6), (1, 5)], {(2, 7): 1, (1, 2): 3, (4, 7): 5, (4, 6): 4, (1, 6): 1, (4, 5): 3, (1, 4): 2, (1, 5): 4, (2, 3): 4, (3, 6): 5, (3, 7): 3, (2, 5): 5, (3, 4): 1, (3, 5): 2}, 5)

([(3, 4), (3, 6), (2, 3), (3, 7), (3, 5), (2, 7), (2, 5), (1, 2), (4, 5), (1, 5), (1, 4), (4, 7), (4, 6), (1, 6)], {(2, 7): 1, (1, 2): 4, (4, 7): 5, (4, 6): 4, (1, 6): 3, (4, 5): 3, (1, 4): 2, (1, 5): 1, (2, 3): 3, (3, 6): 2, (3, 7): 4, (2, 5): 2, (3, 4): 1, (3, 5): 5}, 5)

Zadatak

Osam studentica FOI-a treba posuditi određene knjige u knjižnici i svaku knjigu posuđuju na tjedan dana i pritom mogu posuditi samo jednu knjigu jer gradivo je zahtjevno i teško je dvije knjige proučiti u tjedan dana. U tablici je dani popis studentica kao i knjige koje su potrebne pojedinim studenticama.

studentica knjige
Emina $K_1$, $K_2$, $K_3$
Maja $K_2$, $K_4$, $K_5$, $K_6$
Ana $K_2$, $K_3$, $K_5$, $K_7$
Marina $K_3$, $K_5$
Sandra $K_1$, $K_6$, $K_7$
Sanja $K_2$, $K_4$, $K_6$
Martina $K_4$, $K_5$, $K_7$
Ines $K_3$, $K_6$

Nakon koliko minimalno tjedana će sve studentice posuditi sve knjige koje trebaju? Napravite za svaku studenticu jedan takav raspored posuđivanja knjiga po tjednima koji traje minimalni broj tjedana. Pritom pretpostavljamo da knjižnica ima samo po jedan primjerak pojedine knjige.

Rješenje

Konstruiramo bipartitni graf. U jednoj particiji su studentice, a u drugoj knjige. Pojedina studentica je spojena bridovima sa svim knjigama koje treba. Minimalni broj tjedana je tada jednak bridno kromatskom broju grafa. Svaka boja predstavlja tjedne.

In [90]:
G5=Graph({"Emina":["K1","K2","K3"],"Maja":["K2","K4","K5","K6"], 
          "Ana":["K2","K3","K5","K7"],"Marina":["K3","K5"], 
          "Sandra":["K1","K6","K7"],"Sanja":["K2","K4","K6"], 
          "Martina":["K4","K5","K7"],"Ines":["K3","K6"]})
In [91]:
G5pos={"Emina":[7,0],"Maja":[6,0],"Ana":[5,0],"Marina":[4,0],"Sandra":[3,0],"Sanja":[2,0],"Martina":[1,0],"Ines":[0,0], 
       "K1":[7,3],"K2":[6,3],"K3":[5,3],"K4":[4,3],"K5":[3,3],"K6":[2,3],"K7":[1,3]}
In [92]:
G5.show(pos=G5pos,vertex_size=1500,figsize=(8,4))

Bridno kromatski broj grafa je jednak 4 pa će nakon minimalno 4 tjedna sve studentice posuditi sve knjige koje trebaju.

In [93]:
edge_coloring(G5,value_only=True)
Out[93]:
4

jedno bojanje bridova s minimalnim brojem boja

In [94]:
edge_coloring(G5)
Out[94]:
[[('Ana', 'K3'),
  ('K6', 'Sanja'),
  ('Emina', 'K2'),
  ('K1', 'Sandra'),
  ('K7', 'Martina'),
  ('K5', 'Marina'),
  ('K4', 'Maja')],
 [('Ana', 'K5'),
  ('K6', 'Sandra'),
  ('Emina', 'K3'),
  ('K2', 'Maja'),
  ('K4', 'Martina')],
 [('Ana', 'K2'),
  ('K5', 'Maja'),
  ('K3', 'Marina'),
  ('K7', 'Sandra'),
  ('K4', 'Sanja'),
  ('Ines', 'K6')],
 [('Ana', 'K7'),
  ('K2', 'Sanja'),
  ('Emina', 'K1'),
  ('K6', 'Maja'),
  ('Ines', 'K3'),
  ('K5', 'Martina')]]

Vizualizacija bojanja bridova na slici

In [95]:
G5.show(pos=G5pos,vertex_size=1500,figsize=(8,4),edge_colors=edge_coloring(G5,hex_colors=True))

termini posuđivanja knjiga po tjednima (uzmemo po želji koja će boja predstavljati pojedini tjedan)

In [96]:
table([[" ","Emina","Maja","Ana","Marina","Sandra","Sanja","Martina","Ines"], 
           ["1. tjedan","K2","K6","K7","K3","K1","K4","K5"," "],
           ["2. tjedan","K3","K5","K2"," ","K7"," ","K4","K6"], 
           ["3. tjedan"," ","K2","K5","","","K6"," ","K3"],
           ["4. tjedan","K1","K4","K3","K5","K6","K2","K7"," "]])
Out[96]:
Emina Maja Ana Marina Sandra Sanja Martina Ines
1. tjedan K2 K6 K7 K3 K1 K4 K5
2. tjedan K3 K5 K2 K7 K4 K6
3. tjedan K2 K5 K6 K3
4. tjedan K1 K4 K3 K5 K6 K2 K7

Ručno formiranje gornje tablice je dosta zamorno i dosadno, a i velika je vjerojatnost da negdje pogriješimo. Stoga ćemo implementirati funkciju raspored_termina koja će automatizirati taj postupak, tj. na temelju obojanih bridova će formirati tablicu rasporeda. Spomenuta funkcija ima sljedeće argumente na ulazu:

  • G: bipartitni graf

  • stupac: lista naziva pojedinih termina koji će biti u prvom stupcu tablice rasporeda. Ova lista mora imati broj elemenata jednak bridno kromatskom broju grafa G.

  • particija: ova varijabla može poprimiti jednu od dvije vrijednosti: 1 ili 2. Po defaultu ima vrijednost 1. Zapravo nam govori po kojoj particiji vrhova u bipartitnom grafu G želimo napraviti raspored, da li po prvoj ili po drugoj particiji vrhova. Koja particija vrhova je prva, a koja druga ovisi na kojem se mjestu nalazi u uređenom paru G.bipartite_sets(). To su zapravo vrhovi grafa G koje želimo imati u prvom retku tablice rasporeda.

  • permutacija: ovo je lista svih prirodnih brojeva koji su manji ili jednaki od bridno kromatskog broja grafa G. Svaka boja brida predstavlja jedan termin. Boja koja se u listi edge_coloring(G) nalazi na $k$-tom mjestu predstavlja $k$-ti termin. Ovakvo pravilo vrijedi kada je permutacija=None kako je i stavljeno po defaultu. Ako želimo da bude drukčije, tada to eksplicitno u varijabli permutacija i naglasimo. Na primjer, ako imamo ukupno 4 različita termina, tada na primjer permutacija=[3,2,4,1] znači da će boja iz liste edge_coloring(G) koja je na trećem mjestu u toj listi predstavljati prvi termin, boja koja je na drugom mjestu predstavljat će drugi termin, boja koja je na četvrtom mjestu predstavljat će treći termin, boja koja je na prvom mjestu predstavljat će četvrti termin. Na ovom primjeru permutacija=None zapravo je isto što i permutacija=[1,2,3,4].
In [97]:
def raspored_termina(G,stupac,particija=1,permutacija=None):
    if len(stupac)!=edge_coloring(G,value_only=True):
        return "Error: Broj termina nije jednak bridno kromatskom broju grafa"
    redak=list(G.bipartite_sets()[particija-1])
    bojanje1=edge_coloring(G)
    if permutacija==None:
        bojanje=bojanje1
    else:
        bojanje=[]
        for k in permutacija:
            bojanje.append(bojanje1[k-1])
    d={}
    r=0
    for x in bojanje:
        for y in x:
            if y[0] in redak:
                d[(r,redak.index(y[0]))]=y[1]
            elif y[1] in redak:
                d[(r,redak.index(y[1]))]=y[0]
            else:
                return "Error: problem sa imenima u retku tablice"
        r+=1
    tablica=[[" "]+redak]
    for i in xrange(len(stupac)):
        row=[]
        for j in xrange(len(redak)):
            row.append(d.get((i,j)," "))
        row=[stupac[i]]+row
        tablica.append(row)
    return table(tablica)

Isprobajmo sada našu funkciju na konkretnom primjeru.

In [98]:
raspored_termina(G5,["1. tjedan","2. tjedan","3. tjedan","4. tjedan"])
Out[98]:
Ana Sanja Maja Emina Martina Sandra Marina Ines
1. tjedan K3 K6 K4 K2 K7 K1 K5
2. tjedan K5 K2 K3 K4 K6
3. tjedan K2 K4 K5 K7 K3 K6
4. tjedan K7 K2 K6 K1 K5 K3

Želimo li malo drukčiji raspored po terminima.

In [99]:
raspored_termina(G5,["1. tjedan","2. tjedan","3. tjedan","4. tjedan"],permutacija=[3,4,2,1])
Out[99]:
Ana Sanja Maja Emina Martina Sandra Marina Ines
1. tjedan K2 K4 K5 K7 K3 K6
2. tjedan K7 K2 K6 K1 K5 K3
3. tjedan K5 K2 K3 K4 K6
4. tjedan K3 K6 K4 K2 K7 K1 K5

Želimo li raspored po knjigama, tj. da znamo kod koje se studentice u pojedinom tjednu nalazi pojedina knjiga

In [100]:
raspored_termina(G5,["1. tjedan","2. tjedan","3. tjedan","4. tjedan"],2)
Out[100]:
K3 K2 K1 K7 K6 K5 K4
1. tjedan Ana Emina Sandra Martina Sanja Marina Maja
2. tjedan Emina Maja Sandra Ana Martina
3. tjedan Marina Ana Sandra Ines Maja Sanja
4. tjedan Ines Sanja Emina Ana Maja Martina
In [101]:
raspored_termina(G5,["1. tjedan","2. tjedan","3. tjedan","4. tjedan"],2,[3,4,2,1])
Out[101]:
K3 K2 K1 K7 K6 K5 K4
1. tjedan Marina Ana Sandra Ines Maja Sanja
2. tjedan Ines Sanja Emina Ana Maja Martina
3. tjedan Emina Maja Sandra Ana Martina
4. tjedan Ana Emina Sandra Martina Sanja Marina Maja

Zadatak

Želimo izraditi raspored posjeta pacijenata $P=\{u,v,z,x\}$ koji se trebaju pregledati kod specijalista $S=\{a,b,c,d,e,f,g\}$. Pri tome pacijent treba posjetiti određenog specijalistu kako je dano u tablici susjednosti.

♦ $a$ $b$ $c$ $d$ $e$ $f$ $g$
$u$ 1 1 0 0 0 0 1
$v$ 0 1 1 0 1 0 0
$z$ 1 0 0 1 0 1 0
$x$ 0 0 0 0 1 1 1

Treba napraviti raspored posjeta pacijenata pojedinom specijalistu, ali i raspored za specijaliste da znaju u kojem terminu im dolazi pojedini pacijent. Svaki pregled traje pola sata i počinje se s radom u 8:00h.

Rješenje

Konstruiramo bipartitni graf. U jednoj particiji su pacijenti, a u drugoj specijalisti. Pojedini pacijent je spojena bridovima sa svim specijalistima koje treba posjetiti. Minimalni broj termina je tada jednak bridno kromatskom broju grafa. Svaka boja predstavlja pojedini termin od pola sata.

In [102]:
G6=Graph({"u":["a","b","g"],"v":["b","c","e"],"z":["a","d","f"],"x":["e","f","g"]})
In [103]:
G6poz={"a":[0,0],"b":[1,0],"c":[2,0],"d":[3,0],"e":[4,0],"f":[5,0],"g":[6,0],
       "u":[0.5,3],"v":[1.5,3],"z":[4.5,3],"x":[5.5,3]}
In [104]:
G6.show(pos=G6poz)

Bridno kromatski broj grafa je jednak 3 pa su potrebna minimalno tri različita termina u rasporedu.

In [105]:
edge_coloring(G6,value_only=True)
Out[105]:
3

jedno bojanje bridova s minimalnim brojem boja

In [106]:
edge_coloring(G6)
Out[106]:
[[('a', 'z'), ('b', 'u'), ('e', 'v'), ('g', 'x')],
 [('a', 'u'), ('c', 'v'), ('d', 'z'), ('f', 'x')],
 [('b', 'v'), ('e', 'x'), ('g', 'u'), ('f', 'z')]]

Vizualizacija bojanja bridova na slici

In [107]:
G6.show(pos=G6poz,edge_colors=edge_coloring(G6,hex_colors=True))

jedan mogući raspored termina za liječnike

In [108]:
raspored_termina(G6,["8:00h","8:30h","9:00h"])
Out[108]:
a c b e d g f
8:00h z u v x
8:30h u v z x
9:00h v x u z

jedan mogući raspored termina za pacijente

In [109]:
raspored_termina(G6,["8:00h","8:30h","9:00h"],2)
Out[109]:
x z u v
8:00h g a b e
8:30h f d a c
9:00h e f g b

možemo malo promijeniti termine

In [110]:
raspored_termina(G6,["8:00h","8:30h","9:00h"],1,[2,3,1])
Out[110]:
a c b e d g f
8:00h u v z x
8:30h v x u z
9:00h z u v x
In [111]:
raspored_termina(G6,["8:00h","8:30h","9:00h"],2,[2,3,1])
Out[111]:
x z u v
8:00h f d a c
8:30h e f g b
9:00h g a b e

Sparivanje u grafovima

U SAGE-u se koristi Edmondsov algoritam koji je implementiran u NetworkX modulu za traženje najvećeg sparivanja u bilo kojem jednostavnom grafu. Čak je moguće i traženje težinskog najvećeg sparivanja kod kojeg se u obzir uzimaju i težine bridova. Osim Edmondsovog algoritma dostupan je i algoritam koji koristi formulaciju problema sparivanja preko linearnog programiranja.

U engleskoj literaturi postoje zapravo dva različita pojma vezana uz sparivanje:

  • maximum matching: Ovaj pojam je vezan uz najveće sparivanje. Za sparivanje $M$ u grafu $G$ kažemo da je najveće ako vrijedi da je $k(M)\geq k(M')$ za svako sparivanje $M'$ u grafu $G$. Edmondsov algoritam upravo traži najveće sparivanje u grafu. Jednostavno rečeno, najveće sparivanje u grafu $G$ je svako ono sparivanje koje ima najveći mogući broj bridova, tj. sva ostala sparivanja u grafu $G$ imaju manje ili jednako bridova od sparivanja $M$.

  • maximal matching: Ovaj pojam je vezan uz maksimalno sparivanje. Za sparivanje $M$ u grafu $G$ kažemo da je maksimalno ako vrijedi $M\not\subset M'$ za svako sparivanje $M'\neq M$ u grafu $G$. Ovakvo sparivanje je puno lakše naći i dolje ćemo implementirati algoritam za taj problem. Jednostavno rečeno, maksimalno sparivanje u grafu $G$ je svako ono sparivanje koje nije sadržano niti u jednom drugom sparivanju grafa $G$. Ili još jednostavnije, to je svako ono sparivanje kojemu više ne možemo dodati niti jedan brid.

Mi zapravo često za najveće sparivanje govorimo maksimalno sparivanje, ali moramo biti oprezni ako želimo razlikovati ova dva pojma. Naime, lako se pokaže da vrijedi

Teorem

Ako je $M$ najveće sparivanje u grafu $G$, tada je $M$ i maksimalno sparivanje u grafu $G$.

Napomena

Pazite, obrat ne vrijedi. Drugim riječima, svako najveće sparivanje je ujedno i maksimalno, ali svako maksimalno sparivanje ne mora biti i najveće sparivanje.

Algoritam za maksimalno sparivanje

Algoritam za traženje maksimalnog sparivanja ima vrlo jednostavnu pohlepnu ideju. Algoritam zapravo prolazi kroz sve bridove grafa i ako je promatrani brid moguće dodati u listu tako da se ne pokvare uvjeti sparivanja, tada se taj brid dodaje u listu. Nakon što više nema bridova za dodati, na izlazu se vraća ta lista bridova koja je zapravo maksimalno sparivanje (ali ne mora biti i najveće sparivanje). Naša funkcija maximal_matching je malo općenitijeg karaktera. Naime, ona na ulazu osim grafa G ima i neko sparivanje M1 u grafu G, a na izlazu vraća maksimalno sparivanje koje sadrži sparivanje M1. Po defaultu je stavljeno M1=[ ], tj. ako ništa posebno ne navedemo, algoritam kreće od praznog sparivanja. Ukoliko imamo želju da naše maksimalno sparivanje sadrži određene bridove, onda ih navedemo u listi M1 na ulazu algoritma. Naravno, funkcija maximal_matching prije nego što krene tražiti maksimalno sparivanje koje sadrži sparivanje M1, provjerava da li je M1 zaista sparivanje u grafu G. Ukoliko nije, na izlazu vraća određenu poruku. Algoritam je i randomiziran tako da u svakom koraku na slučajni način bira neki od još neprovjerenih bridova.

In [112]:
def maximal_matching(G,M1=[]):
    M=M1[:]
    bridovi=G.edges(labels=False)
    provjera=[]
    if M!=[]:
        for (u,v) in M:
            if not(((u,v) in bridovi) or ((v,u) in bridovi)):
                return "Error: U sparivanju M su nepostojeci bridovi."
        for (u,v) in M:
            if ((u in provjera) or (v in provjera)):
                return "Error: M nije sparivanje u grafu G."
            else:
                provjera.extend([u,v])
    bridovi=list(set(bridovi).difference(set(M)))
    while bridovi != []:
        b=choice(bridovi)
        if not((b[0] in provjera) or (b[1] in provjera)):
            M.append(b)
            provjera.extend([b[0],b[1]])
        bridovi.remove(b)
    return M

Zadatak

Pet neudatih djevojaka ima određeni broj neoženjenih prijatelja kako je prikazano u sljedećoj tablici.

djevojke neoženjeni prijatelji
Sandra Ivan, Miroslav, Marijan, Danijel
Maja Miroslav, Franjo
Ana Ivan, Marijan
Emina Marijan, Danijel
Ines Miroslav, Marijan
  • Svaka se djevojka želi udati za nekog od svojih prijatelja. Da li je moguće svakoj od djevojaka ostvariti njihove želje? Ukoliko je to moguće, pronađite način kako to ostvariti. Ako je nemoguće ispuniti želju svakoj od djevojaka, objasnite zašto to nije moguće. Problem modelirajte pomoću grafova i objasnite svaku svoju tvrdnju.

  • Zamislimo ovakvu situaciju. Maja se želi udati za svojeg prijatelja Miroslava i trudi se da ga osvoji. Pretpostavimo da joj je to uspjelo i da ju je Miroslav oženio. Da li je na taj način Maja unesrećila neku od preostalih djevojaka u smislu da se ta djevojka nije mogla udati za nekog od svojih prijatelja? Da li je moguće u toj situaciji spasiti preostale djevojke osim Sandre tako da se svaka od njih uda za nekog od svojih prijatelja? Koje bi mogućnosti u tom slučaju imala Sandra? Obrazložite jasno i precizno svaki svoj odgovor.

Rješenje

Konstruiramo bipartitni graf. U jednoj particiji su djevojke, a u drugoj neoženjeni prijatelji. Svaka djevojka je u grafu susjedna samo sa svojim prijateljima.

In [113]:
G7=Graph({"Sandra":["Ivan","Miroslav","Marijan","Danijel"],"Maja":["Miroslav","Franjo"], 
          "Ana":["Ivan","Marijan"],"Emina":["Marijan","Danijel"],"Ines":["Miroslav","Marijan"]})
In [114]:
G7pos={"Sandra":[0,0],"Maja":[2,0],"Ana":[4,0],"Emina":[6,0],"Ines":[8,0],"Ivan":[0,3],
       "Miroslav":[2,3],"Marijan":[4,3],"Danijel":[6,3],"Franjo":[8,3]}
In [115]:
G7.show(pos=G7pos,vertex_size=1800,figsize=(8,6))

Moguće je svakoj djevojci ostvariti njezinu želju zato jer najveće sparivanje u promatranom bipartitnom grafu ima ukupno 5 bridova pa je to ujedno i savršeno sparivanje.

In [116]:
G7.matching(value_only=True)
Out[116]:
5

jedan način ispunjavanja želja svih djevojaka

In [117]:
G7.matching()
Out[117]:
[('Maja', 'Franjo', None),
 ('Danijel', 'Emina', None),
 ('Ivan', 'Ana', None),
 ('Sandra', 'Miroslav', None),
 ('Ines', 'Marijan', None)]

sparivanje prikazano na grafu

In [118]:
sparivanje=map(lambda x: x[0:-1],G7.matching())
G7.show(pos=G7pos,edge_colors={"blue":sparivanje},vertex_size=1800,figsize=(8,6),)

drugi dio zadatka

Ako se Maja udala za Miroslava, tada će Franjo sigurno ostati neoženjen jer se on jedino sviđao Maji. Dakle, Maja će svojom udajom za Miroslava, sigurno unesrećiti neku od preostalih djevojaka u smislu da se neka od njih neće moći udati za neku od svojih simpatija.

Ukoliko se Maja uda za Miroslava, preostale djevojke osim Sandre je moguće spasiti na sljedeći način: Ines se udaje za Marijana, Emina za Danijela, Ana za Ivana. U tom slučaju Sandra ima mogućnost da se uda za Franju (iako on nije njezina simpatija) ili može ostati slobodna cura. :-)

Isprobajmo i našu funkciju maximal_matching koja će tražiti maksimalno sparivanje koje sadrži brid {Maja, Miroslav}. Vidimo da u 20 pokretanja ove funkcije čak možemo i dvije djevojke razočarati, tj. postoji maksimalno sparivanje sa samo tri brida koje sadrži brid {Maja, Miroslav}. Nadalje, moguće je da u svakom od tih maksimalnih sparivanja Sandra nikad nije razočarana. Naime, postoji puno bridova s kojima je Sandra susjedna pa je zato i velika vjerojatnost da će naša randomizirana funkcija odabrati ranije neki od tih bridova.

In [119]:
for k in xrange(20):
    print maximal_matching(G7,[('Maja','Miroslav')])

[('Maja', 'Miroslav'), ('Danijel', 'Sandra'), ('Ana', 'Ivan'), ('Ines', 'Marijan')]
[('Maja', 'Miroslav'), ('Ines', 'Marijan'), ('Ana', 'Ivan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Danijel', 'Emina'), ('Ana', 'Marijan'), ('Ivan', 'Sandra')]
[('Maja', 'Miroslav'), ('Ines', 'Marijan'), ('Danijel', 'Emina'), ('Ana', 'Ivan')]
[('Maja', 'Miroslav'), ('Ana', 'Ivan'), ('Emina', 'Marijan'), ('Danijel', 'Sandra')]
[('Maja', 'Miroslav'), ('Ivan', 'Sandra'), ('Emina', 'Marijan')]
[('Maja', 'Miroslav'), ('Ines', 'Marijan'), ('Danijel', 'Emina'), ('Ivan', 'Sandra')]
[('Maja', 'Miroslav'), ('Ivan', 'Sandra'), ('Emina', 'Marijan')]
[('Maja', 'Miroslav'), ('Marijan', 'Sandra'), ('Ana', 'Ivan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Danijel', 'Emina'), ('Ana', 'Ivan'), ('Marijan', 'Sandra')]
[('Maja', 'Miroslav'), ('Ines', 'Marijan'), ('Danijel', 'Sandra'), ('Ana', 'Ivan')]
[('Maja', 'Miroslav'), ('Ana', 'Marijan'), ('Ivan', 'Sandra'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Danijel', 'Emina'), ('Ines', 'Marijan'), ('Ana', 'Ivan')]
[('Maja', 'Miroslav'), ('Ana', 'Ivan'), ('Ines', 'Marijan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Marijan', 'Sandra'), ('Danijel', 'Emina'), ('Ana', 'Ivan')]
[('Maja', 'Miroslav'), ('Danijel', 'Sandra'), ('Emina', 'Marijan'), ('Ana', 'Ivan')]
[('Maja', 'Miroslav'), ('Marijan', 'Sandra'), ('Ana', 'Ivan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Danijel', 'Sandra'), ('Emina', 'Marijan'), ('Ana', 'Ivan')]
[('Maja', 'Miroslav'), ('Danijel', 'Emina'), ('Ivan', 'Sandra'), ('Ana', 'Marijan')]
[('Maja', 'Miroslav'), ('Ana', 'Marijan'), ('Ivan', 'Sandra'), ('Danijel', 'Emina')]

Ako nam se ne pojavi maksimalno sparivanje bez Sandre koje sadrži brid {Maja, Miroslav} u prvih 20 pokretanja, možemo probati algoritam pokrenuti više od 20 puta i čekati tako dugo dok se eventualno ne pojavi takvo sparivanje.

In [120]:
for k in xrange(100):
    spar=maximal_matching(G7,[('Maja','Miroslav')])
    prvi=map(lambda x:x[0],spar)
    drugi=map(lambda x:x[1],spar)
    if not(('Sandra' in prvi) or ('Sandra' in drugi)):
        print k+1,'. korak',spar
        break
    elif k==99:
        print 'Sandra ne odustaje od udaje. :-)'

1 . korak [('Maja', 'Miroslav'), ('Ines', 'Marijan'), ('Ana', 'Ivan'), ('Danijel', 'Emina')]

ili još bolje, izbrišemo sve bridove koji su susjedni sa vrhom 'Sandra' i tada relativno brzo dobijemo željeno sparivanje

In [121]:
bridoviSandra=filter(lambda x: (x[0]=='Sandra') or (x[1]=='Sandra'),G7.edges())
G7.delete_edges(bridoviSandra)
for k in xrange(10):
    print maximal_matching(G7,[('Maja','Miroslav')])

[('Maja', 'Miroslav'), ('Danijel', 'Emina'), ('Ana', 'Ivan'), ('Ines', 'Marijan')]
[('Maja', 'Miroslav'), ('Ana', 'Marijan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Danijel', 'Emina'), ('Ana', 'Ivan'), ('Ines', 'Marijan')]
[('Maja', 'Miroslav'), ('Ines', 'Marijan'), ('Ana', 'Ivan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Ines', 'Marijan'), ('Ana', 'Ivan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Ana', 'Marijan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Danijel', 'Emina'), ('Ana', 'Marijan')]
[('Maja', 'Miroslav'), ('Ana', 'Marijan'), ('Danijel', 'Emina')]
[('Maja', 'Miroslav'), ('Emina', 'Marijan'), ('Ana', 'Ivan')]
[('Maja', 'Miroslav'), ('Ana', 'Marijan'), ('Danijel', 'Emina')]

Zadatak

Nina, Danijela, Sandra, Iva, Renata, Mirela i Marija poznaju neke od mladića $M_1,\ldots,M_8$. Preciznije, Nina poznaje mladiće $M_1$, $M_2$ i $M_6$. Danijela poznaje $M_2$, $M_3$ i $M_6$. Sandra poznaje $M_1$, $M_3$ i $M_5$. Iva poznaje $M_4$, $M_7$ i $M_8$. Renata poznaje $M_1$, $M_5$ i $M_6$. Mirela poznaje $M_1$, $M_3$ i $M_6$. Marija poznaje $M_3$, $M_5$ i $M_6$.

  • Svaka od djevojaka ima veliku želju udati se za nekog od mladića kojeg poznaje. Dokažite da je to unatoč njihovim silnim željama ipak nemoguće.
  • Pronađite jedan mogući način udavanja tih djevojaka tako da čim manje djevojaka bude razočarano. Djevojka je po definiciji razočarana ako se nije uspjela udati za mladića kojeg poznaje.

Rješenje

Konstruiramo bipartitni graf. U jednoj particiji su djevojke, a u drugoj mladići. Djevojke su susjedne samo s onim mladićima koje poznaju.

In [122]:
G8=Graph({"Nina":["M1","M2","M6"],"Danijela":["M2","M3","M6"],"Sandra":["M1","M3","M5"], "Iva":["M4","M7","M8"],
          "Renata":["M1","M5","M6"],"Mirela":["M1","M3","M6"],"Marija":["M3","M5","M6"]})
In [123]:
G8pos={"Nina":[0,0],"Danijela":[2,0],"Sandra":[4,0],"Iva":[6,0],"Renata":[8,0],"Mirela":[10,0],"Marija":[12,0], 
       "M1":[-0.5,3],"M2":[1.5,3],"M3":[3.5,3],"M4":[5.5,3],"M5":[7.5,3],"M6":[9.5,3],"M7":[11.5,3],"M8":[13.5,3]}
In [124]:
G8.show(pos=G8pos,vertex_size=1700,figsize=(12,10))

Nije moguće ispuniti želje svim djevojkama jer najveće sparivanje u grafu ima samo 6 elemenata, a djevojaka je ukupno 7.

In [125]:
G8.matching(value_only=True)
Out[125]:
6

Kada ručno rješavamo, trebamo se pozvati na Hallov teorem.

Naime, ako uzmemo, $T\subseteq X$, $T=\{\text{Nina}, \text{Danijela}, \text{Sandra}, \text{Renata}, \text{Mirela}, \text{Marija}\}$, tada je $S(T)=\{M_1, M_2, M_3, M_5, M_6\}$. No, tada je kardinalni broj skupa $S(T)$ strogo manji od kardinalnog broja skupa $T$ pa prema Hallovom teoremu ne postoji sparivanje koje zasićuje svaki vrh iz $X$.

Jedan mogući način udavanja u kojemu je čim manje djevojaka razočarano (u ovom slučaju je samo Nina razočarana)

In [126]:
G8.matching()
Out[126]:
[('M1', 'Sandra', None),
 ('M3', 'Mirela', None),
 ('Danijela', 'M2', None),
 ('M6', 'Renata', None),
 ('M5', 'Marija', None),
 ('Iva', 'M8', None)]
In [127]:
sparivanje2=map(lambda x: x[0:-1],G8.matching())
G8.show(pos=G8pos,edge_colors={"blue":sparivanje2},vertex_size=1700,figsize=(12,10))

Zadatak

Osam djevojaka su odlučile otići tjedan dana na veslanje u predivnu prirodu. Kako na tom mjestu u toj predivnoj prirodi postoje samo četiri čamca u koje stanu po dvije djevojke, one se moraju podijeliti u parove. Međutim, neke od djevojaka ne žele veslati zajedno iz nekih privatnih razloga. Sljedeća tablica nam razotkriva koje djevojke žele zajedno veslati. Ako neke dvije djevojke žele zajedno veslati, u tablici je odgovarajuće mjesto označeno s 1. Ako je neko mjesto u tablici označeno s 0, tada odgovarajuće djevojke ne žele zajedno veslati.

♦ Marija Janja Ivana Sandra Danijela Katarina Petra Dijana
Marija ♦ 0 0 0 1 1 0 1
Janja 0 ♦ 0 1 1 1 0 0
Ivana 0 0 ♦ 1 0 0 1 1
Sandra 0 1 1 ♦ 0 0 1 0
Danijela 1 1 0 0 ♦ 0 0 1
Katarina 1 1 0 0 0 ♦ 0 1
Petra 0 0 1 1 0 0 ♦ 0
Dijana 1 0 1 0 1 1 0 ♦
  • Pronađite jedan mogući način podjele djevojaka u parove za veslanje ukoliko je to moguće.
  • Kako to obično bude, na pola putovanja do te predivne prirode neke su se djevojke malo posvađale tako da su neke od njih čak odustale da zajedno budu u paru, iako je prije postojala mogućnost da zajedno veslaju. Dijana i Ivana više ne žele veslati zajedno, te isto tako Janja i Sandra. Da li je sada u ovom slučaju moguće djevojke rasporediti u parove za veslanje?

Rješenje

Konstruirat ćemo graf u kojemu će vrhovi biti djevojke, a dva vrha su spojena bridom jedino ako pripadne djevojke žele zajedno veslati. Tada u dobivenom grafu želimo naći savršeno sparivanje ukoliko ono postoji.

In [128]:
M=matrix([[0,0,0,0,1,1,0,1], [0,0,0,1,1,1,0,0], [0,0,0,1,0,0,1,1], [0,1,1,0,0,0,1,0], 
          [1,1,0,0,0,0,0,1], [1,1,0,0,0,0,0,1], [0,0,1,1,0,0,0,0], [1,0,1,0,1,1,0,0]])
In [129]:
G9=Graph(M)
rj=dict(zip(range(8),['Marija','Janja','Ivana','Sandra','Danijela','Katarina','Petra','Dijana']))
G9.relabel(rj)

Uočite da G9 nije bipartitni graf jer sadrži cikluse neparnih duljina.

In [130]:
G9.is_bipartite()
Out[130]:
False
In [131]:
G9.show(layout='circular',vertex_size=1800,figsize=(5,5))

Kako najveće sparivanje ima 4 brida, a graf ima 8 vrhova, to sparivanje je ujedno i savršeno sparivanje. Stoga se djevojke mogu grupirati u parove za veslanje tako da svaka djevojka vesla s nekom od djevojaka s kojom zaista želi veslati.

In [132]:
G9.matching(value_only=True)
Out[132]:
4

jedan način grupiranja djevojaka u parove

In [133]:
G9.matching()
Out[133]:
[('Marija', 'Katarina', None),
 ('Ivana', 'Petra', None),
 ('Janja', 'Sandra', None),
 ('Dijana', 'Danijela', None)]
In [134]:
G9.show(layout='circular',edge_colors={"blue":G9.matching()},vertex_size=1800,figsize=(5,5))

No, nakon svađe situacija postaje ozbiljnija :-)

In [135]:
G9.delete_edges([('Dijana','Ivana'),('Janja','Sandra')])
In [136]:
G9.show(layout='circular',vertex_size=1800,figsize=(5,5))

Kako najveće sparivanje ima samo 3 brida u grafu od 8 vrhova, zaključujemo da u zadanom grafu nema savršenog sparivanja pa se u ovom slučaju djevojke ne mogu rasporediti u parove za veslanje tako da svaka djevojka vesla s nekom od djevojaka s kojom zaista želi veslati.

In [137]:
G9.matching(value_only=True)
Out[137]:
3

Jedno najveće sparivanje u kojemu su Janja i Petra ostale bez svojeg para pa bi bile prisiljene zajedno veslati, iako one ne žele zajedno veslati.

In [138]:
G9.matching()
Out[138]:
[('Danijela', 'Marija', None),
 ('Ivana', 'Sandra', None),
 ('Dijana', 'Katarina', None)]
In [139]:
G9.show(layout='circular',edge_colors={"blue":G9.matching()},vertex_size=1800,figsize=(5,5))
In [ ]: