s spodnjo funkcijo generiramo vse eno ciklične grafe na n vozliščih. Funkcija deluje počasi že za 8 vozlišč. grafov je takrat že več 89 tako, da celostno analizo za večje število vozlič sploh ni smiselno računati.
In [3]:
eno_ciklicni =[]
for G in graphs(5, size=5):
if G.is_connected():
if len(G.cycle_basis('vertex')) == 1:
eno_ciklicni.append(G)
#G.show()
In [4]:
len(eno_ciklicni)
Out[4]:
5
In [1]:
def AZIvrednost(graf, alpha=3): #Izračun AZI vrednost za nek graf
vsota = 0
for u in graf:
for v in graf[u]:
vsota = vsota + ((len(graf[u]) *len(graf[v]))/(len(graf[u]) + len(graf[v]) - 2))^(alpha)
return vsota/2
In [6]:
AZI_vred = {}
for G in eno_ciklicni:
a = AZIvrednost(G, 3)
AZI_vred[a] = (G)
poračunamo ekstremalne vrednosti AZI za vse enciklične grafe in jo izpišemo skupaj z pripadajočim grafom
In [7]:
print(max(AZI_vred))
AZI_vred[max(AZI_vred)]
40
Out[7]:
In [8]:
print(min(AZI_vred))
AZI_vred[min(AZI_vred)]
776/27
Out[8]:
Za velika števila bomo poizkušali rezultat dobiti z iskanjem maksimuma po metodi spreminjanja do sedaj najbolše metode, dela do n=40
In [9]:
def generiranje_grafa(n):
A = graphs.RandomTree(n)
A.add_edge(A.complement().random_edge(labels=False))
return A
In [10]:
graf = B = generiranje_grafa(10)
B.show()
Out[10]:
In [11]:
from random import choice
def minima(graf, n=100, alpha=3):
najboljsa = trenutna = AZIvrednost(graf, alpha)
najboljsi_graf = graf
for j in range(n):
T = n/(j+1)
e = graf.random_edge(labels=False)
K = Graph(graf)
K.delete_edge(e)
if K.is_connected():
e = K.complement().random_edge()
else:
A, B = K.connected_components()
e = (choice(A), choice(B))
K.add_edge(e)
a = AZIvrednost(K, alpha)
if a < najboljsa:
najboljsi_graf = K
najboljsa = a
if a < trenutna or exp((trenutna - a) / T) > random():
graf = K
trenutna = a
najboljsi_graf.show()
return (najboljsi_graf, najboljsa)
In [12]:
from random import choice
def maxima(graf, n=100, alpha=3):
najboljsa = trenutna = AZIvrednost(graf, alpha)
najboljsi_graf = graf
for j in range(n):
T = n/(j+1)
e = graf.random_edge(labels=False)
K = Graph(graf)
K.delete_edge(e)
if K.is_connected():
e = K.complement().random_edge()
else:
A, B = K.connected_components()
e = (choice(A), choice(B))
K.add_edge(e)
a = AZIvrednost(K, alpha)
if a > najboljsa:
najboljsi_graf = K
najboljsa = a
if a > trenutna or exp((trenutna - a) / T) > random():
graf = K
trenutna = a
najboljsi_graf.show()
return (najboljsi_graf, najboljsa)
In [18]:
graf = B = generiranje_grafa(50)
maxima(B, 100000)
Out[18]:
Out[18]:
(Graph on 50 vertices, 5920376509/12348000)
In [19]:
minima(B, 100000)
Out[19]:
Out[19]:
(Graph on 50 vertices, 989986522/7414875)
In [2]:
import json
In [12]:
with open("max3_100_100.json") as f:
Gmax = Graph(str(json.load(f)), loops=False, multiedges=False)
Gmax.plot()
Out[12]:
In [14]:
with open("min3_100_100.json") as f:
Gmin = Graph(str(json.load(f)), loops=False, multiedges=False)
Gmin.plot()
Out[14]:
In [3]:
with open("max3_50_50.json") as f:
Gmax = Graph(str(json.load(f)), loops=False, multiedges=False)
print(N(AZIvrednost(Gmax)))
Gmax.plot()
535.542522711899
Out[3]:
In [4]:
with open("min3_50_50.json") as f:
Gmin = Graph(str(json.load(f)), loops=False, multiedges=False)
print(N(AZIvrednost(Gmin)))
Gmin.plot()
114.634171687723
Out[4]:
In [5]:
with open("max3_20_20.json") as f:
G20max = Graph(str(json.load(f)), loops=False, multiedges=False)
print(N(AZIvrednost(G20max)))
G20max.plot()
221.429586895122
Out[5]:
In [6]:
with open("min3_20_20.json") as f:
G20min = Graph(str(json.load(f)), loops=False, multiedges=False)
print(N(AZIvrednost(G20min)))
G20min.plot()
43.9936556927298
Out[6]:
