verzija: SageMath 8.4
$K_{2,3}$ je planarni graf
K23=graphs.CompleteBipartiteGraph(2,3)
K23.is_planar()
K23.show()
neko planarno smještenje od $K_{2,3}$
poz=K23.layout_planar();poz
K23.show(pos=poz)
možemo i direktno dobiti sliku bez posebnog računanja pozicija vrhova
K23.show(layout='planar')
$K_{3,3}$ nije planarni graf
graphs.CompleteBipartiteGraph(3,3).is_planar()
$K_5$ nije planarni graf
graphs.CompleteGraph(5).is_planar()
Petersenov graf nije planarni graf
graphs.PetersenGraph().is_planar()
$K_4$ je planarni graf
graphs.CompleteGraph(4).is_planar()
graphs.CompleteGraph(4).show()
neko ravninsko smještenje od $K_4$
graphs.CompleteGraph(4).show(layout='planar')
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')
tijela.show(aspect_ratio=[1,1,1],frame=False,viewer='threejs',online=True)
3D tijelo
cube(color='yellow',frame=False,viewer='threejs',online=True)
pripadni graf
graphs.CubeGraph(3).show(vertex_labels=False,layout='spring')
neko planarno smještenje
$\nu=8, \varepsilon=12, \Phi=6,\quad \nu-\varepsilon+\Phi=2$
graphs.CubeGraph(3).show(vertex_labels=False,vertex_size=50,layout='planar')
3D graf
graphs.CubeGraph(3).show3d(viewer='threejs',online=True)
3D tijelo
tetrahedron(color='yellow',frame=False,viewer='threejs',online=True)
pripadni graf
graphs.TetrahedralGraph().show(vertex_labels=False,layout='spring')
neko planarno smještenje
$\nu=4, \varepsilon=6, \Phi=4,\quad \nu-\varepsilon+\Phi=2$
graphs.TetrahedralGraph().show(vertex_labels=False,layout='planar')
3D graf
graphs.TetrahedralGraph().show3d(viewer='threejs',online=True)
3D tijelo
octahedron(color='yellow',frame=False,viewer='threejs',online=True)
pripadni graf
graphs.OctahedralGraph().show(vertex_labels=False,layout='spring')
neko planarno smještenje
$\nu=6, \varepsilon=12, \Phi=8,\quad \nu-\varepsilon+\Phi=2$
graphs.OctahedralGraph().show(vertex_labels=False,vertex_size=40,layout='planar')
3D graf
graphs.OctahedralGraph().show3d(viewer='threejs',online=True)
3D tijelo
dodecahedron(color='pink',frame=False,viewer='threejs',online=True)
pripadni graf
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$
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
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]}
graphs.DodecahedralGraph().show(pos=pozicijeDOD,vertex_size=150)
3D graf
graphs.DodecahedralGraph().show3d(viewer='threejs',online=True)
3D tijelo
icosahedron(color='yellow',frame=False,viewer='threejs',online=True)
pripadni graf
graphs.IcosahedralGraph().show(vertex_labels=False,vertex_size=40)
neko planarno smještenje
$\nu=12, \varepsilon=30, \Phi=20,\quad \nu-\varepsilon+\Phi=2$
graphs.IcosahedralGraph().show(vertex_labels=False,vertex_size=20,layout='planar')
3D graf
graphs.IcosahedralGraph().show3d(viewer='threejs',online=True)
Ispitajte da li je zadani graf planarni i u slučaju da jest pronađite jedno njegovo ravninsko smještenje.
H=Graph({1:[2,5,6],2:[3,4,5],3:[4,5,6],4:[5],5:[6]})
Zadani graf jest planarni
H.is_planar()
jedno njegovo ravninsko smještenje
H.show(layout='planar')
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.
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
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.
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.
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.
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())))
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?
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.
G1=Graph({"fizika":["matematika","engleski","geografija","ekonomija","plivanje","statistika"],
"matematika":["engleski","poslovanje","geografija"],
"geografija":["ekonomija","poslovanje"],
"statistika":["ekonomija","poslovanje","plivanje"],
"ekonomija":["plivanje"]})
G1.show(layout="circular",vertex_size=3700,figsize=(5,5))
Kromatski broj grafa je 4 pa su potrebna najmanje 4 različita termina.
G1.chromatic_number()
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).
G1.coloring()
želimo li to prikazati vizualno na samom grafu
bojanje1=G1.coloring(hex_colors=True);bojanje1
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}.
G1.clique_number()
G1.clique_maximum()
i samo je jedna takva najveća klika u promatranom grafu
G1.cliques_maximum()
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?
for k in xrange(50):
print random_bojanje(G1)
for k in xrange(10):
print Welsh_Powell(G1)
for k in xrange(10):
print Brelaz(G1)
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.
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.
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"]})
G2.show(layout="circular",figsize=(4,4))
Kromatski broj grafa je 5 pa je potrebno minimalno 5 različitih kanala.
G2.chromatic_number()
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.
G2.coloring()
želimo li to prikazati vizualno na samom grafu
boje2=G2.coloring(hex_colors=True);boje2
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}.
G2.clique_number()
G2.clique_maximum()
G2.cliques_maximum()
Promatrani graf nije planarni jer sadrži podgraf $K_5$ koji nije planarni.
G2.is_planar()
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.
for k in xrange(30):
print random_bojanje(G2)
for k in xrange(10):
print Welsh_Powell(G2)
for k in xrange(10):
print Brelaz(G2)
Pokažite da Brelazov i Welsh-Powellov algoritam ne daju uvijek bojanje vrhova s minimalnim brojem boja u grafu
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.
G3.chromatic_number()
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).
for k in xrange(20):
print Brelaz(G3)
for k in xrange(20):
print Welsh_Powell(G3)
from sage.graphs.graph_coloring import edge_coloring
Odredite kromatski i bridno kromatski broj grafa
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]}
G4.show(pos=G4poz)
Kromatski broj grafa je 3.
G4.chromatic_number()
Jedno bojanje vrhova s minimalnim brojem boja
G4.coloring()
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.
for k in xrange(20):
print random_bojanje(G4)
for k in xrange(20):
print Welsh_Powell(G4)
for k in xrange(20):
print Brelaz(G4)
Bridno kromatski broj grafa je 5.
edge_coloring(G4,value_only=True)
Jedno bojanje bridova s minimalnim brojem boja. Bridovima iz istog elementa particije bridova je pridružena ista boja.
edge_coloring(G4)
Vizualizacija obojenih bridova na slici
boje_bridova=edge_coloring(G4,hex_colors=True);boje_bridova
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.
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.
for k in xrange(10):
print random_bojanje(G4line)
print
for k in xrange(10):
print Welsh_Powell(G4line)
print
for k in xrange(10):
print Brelaz(G4line)
print
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.
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.
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"]})
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]}
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.
edge_coloring(G5,value_only=True)
jedno bojanje bridova s minimalnim brojem boja
edge_coloring(G5)
Vizualizacija bojanja bridova na slici
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)
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"," "]])
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:
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.
raspored_termina(G5,["1. tjedan","2. tjedan","3. tjedan","4. tjedan"])
Želimo li malo drukčiji raspored po terminima.
raspored_termina(G5,["1. tjedan","2. tjedan","3. tjedan","4. tjedan"],permutacija=[3,4,2,1])
Želimo li raspored po knjigama, tj. da znamo kod koje se studentice u pojedinom tjednu nalazi pojedina knjiga
raspored_termina(G5,["1. tjedan","2. tjedan","3. tjedan","4. tjedan"],2)
raspored_termina(G5,["1. tjedan","2. tjedan","3. tjedan","4. tjedan"],2,[3,4,2,1])
Ž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.
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.
G6=Graph({"u":["a","b","g"],"v":["b","c","e"],"z":["a","d","f"],"x":["e","f","g"]})
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]}
G6.show(pos=G6poz)
Bridno kromatski broj grafa je jednak 3 pa su potrebna minimalno tri različita termina u rasporedu.
edge_coloring(G6,value_only=True)
jedno bojanje bridova s minimalnim brojem boja
edge_coloring(G6)
Vizualizacija bojanja bridova na slici
G6.show(pos=G6poz,edge_colors=edge_coloring(G6,hex_colors=True))
jedan mogući raspored termina za liječnike
raspored_termina(G6,["8:00h","8:30h","9:00h"])
jedan mogući raspored termina za pacijente
raspored_termina(G6,["8:00h","8:30h","9:00h"],2)
možemo malo promijeniti termine
raspored_termina(G6,["8:00h","8:30h","9:00h"],1,[2,3,1])
raspored_termina(G6,["8:00h","8:30h","9:00h"],2,[2,3,1])
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:
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.
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
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 |
Konstruiramo bipartitni graf. U jednoj particiji su djevojke, a u drugoj neoženjeni prijatelji. Svaka djevojka je u grafu susjedna samo sa svojim prijateljima.
G7=Graph({"Sandra":["Ivan","Miroslav","Marijan","Danijel"],"Maja":["Miroslav","Franjo"],
"Ana":["Ivan","Marijan"],"Emina":["Marijan","Danijel"],"Ines":["Miroslav","Marijan"]})
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]}
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.
G7.matching(value_only=True)
jedan način ispunjavanja želja svih djevojaka
G7.matching()
sparivanje prikazano na grafu
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.
for k in xrange(20):
print maximal_matching(G7,[('Maja','Miroslav')])
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.
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. :-)'
ili još bolje, izbrišemo sve bridove koji su susjedni sa vrhom 'Sandra' i tada relativno brzo dobijemo željeno sparivanje
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')])
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$.
Konstruiramo bipartitni graf. U jednoj particiji su djevojke, a u drugoj mladići. Djevojke su susjedne samo s onim mladićima koje poznaju.
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"]})
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]}
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.
G8.matching(value_only=True)
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)
G8.matching()
sparivanje2=map(lambda x: x[0:-1],G8.matching())
G8.show(pos=G8pos,edge_colors={"blue":sparivanje2},vertex_size=1700,figsize=(12,10))
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 | ♦ |
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.
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]])
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.
G9.is_bipartite()
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.
G9.matching(value_only=True)
jedan način grupiranja djevojaka u parove
G9.matching()
G9.show(layout='circular',edge_colors={"blue":G9.matching()},vertex_size=1800,figsize=(5,5))
No, nakon svađe situacija postaje ozbiljnija :-)
G9.delete_edges([('Dijana','Ivana'),('Janja','Sandra')])
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.
G9.matching(value_only=True)
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.
G9.matching()
G9.show(layout='circular',edge_colors={"blue":G9.matching()},vertex_size=1800,figsize=(5,5))