In [68]:
from sage.graphs.trees import TreeIterator
drevo = []
for G in TreeIterator(6):
if G.is_connected():
if len(G.cycle_basis('vertex')) == 0:
drevo.append(G)
G.show()
Out[68]:
Out[68]:
Out[68]:
Out[68]:
Out[68]:
Out[68]:
In [69]:
def AZIvrednost(graf, alpha): #Izračun AZI vrednost za nek graf, len(graf[u]) nam da dolžino seznama sosedovza vozlišče u, torej je to stopnja vozlišča u
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 [70]:
alpha = -3
AZI_vred = {}
for G in drevo:
a = AZIvrednost(G, alpha)
AZI_vred[a] = (G)
In [71]:
print(max(AZI_vred))
AZI_vred[max(AZI_vred)]
64/25
Out[71]:
In [72]:
print(min(AZI_vred))
AZI_vred[min(AZI_vred)]
5/8
Out[72]:
In [73]:
alpha = -2
AZI_vred = {}
for G in drevo:
a = AZIvrednost(G, alpha)
AZI_vred[a] = (G)
In [74]:
print(max(AZI_vred))
AZI_vred[max(AZI_vred)]
16/5
Out[74]:
In [75]:
print(min(AZI_vred))
AZI_vred[min(AZI_vred)]
5/4
Out[75]:
In [76]:
alpha = -1
AZI_vred = {}
for G in drevo:
a = AZIvrednost(G, alpha)
AZI_vred[a] = (G)
In [77]:
print(max(AZI_vred))
AZI_vred[max(AZI_vred)]
4
Out[77]:
In [78]:
print(min(AZI_vred))
AZI_vred[min(AZI_vred)]
5/2
Out[78]:
In [79]:
alpha = 0
AZI_vred = {}
for G in drevo:
a = AZIvrednost(G, alpha)
AZI_vred[a] = (G)
In [80]:
print(max(AZI_vred))
AZI_vred[max(AZI_vred)]
5
Out[80]:
In [81]:
print(min(AZI_vred))
AZI_vred[min(AZI_vred)]
5
Out[81]:
In [82]:
alpha = 8
AZI_vred = {}
for G in drevo:
a = AZIvrednost(G, alpha)
AZI_vred[a] = (G)
In [83]:
print(max(AZI_vred))
AZI_vred[max(AZI_vred)]
1280
Out[83]:
In [84]:
print(min(AZI_vred))
AZI_vred[min(AZI_vred)]
1953125/65536
Out[84]:
In [85]:
alpha = 2
AZI_vred = {}
for G in drevo:
a = AZIvrednost(G, alpha)
AZI_vred[a] = (G)
In [86]:
print(max(AZI_vred))
AZI_vred[max(AZI_vred)]
20
Out[86]:
In [87]:
print(min(AZI_vred))
AZI_vred[min(AZI_vred)]
125/16
Out[87]:
In [88]:
alpha = 3
AZI_vred = {}
for G in drevo:
a = AZIvrednost(G, alpha)
AZI_vred[a] = (G)
In [89]:
print(max(AZI_vred))
AZI_vred[max(AZI_vred)]
40
Out[89]:
In [90]:
print(min(AZI_vred))
AZI_vred[min(AZI_vred)]
625/64
Out[90]:
Če primerjamo različne alfa lahko opazimo najprej, da pri alfa = 0 ima graf maksimalno in minimalno AZI vrednost pri istem grafu. Zanimivo je to, da pri alfa z negativnimi vrednostmi ima zvezda maksimalno AZI vrednost, kar je obratno od alfa s pozitivnimi vrednostmi. Opazimo tudi to, da naprimer en graf, ki ima maksimalno AZI vrednost npr pri alfa = -1, isti graf ima minimalno AZI vrednost pri alfa = 1 in tisti graf ki ima pri alfa = -1 minimalno AZI vrednost ima pri alfa = 1 maksimalno AZI vrednost.
In [91]:
def generiranje_dreves(n):
A = graphs.RandomTree(n)
return A
In [92]:
test = Graph({0: [1, 2, 3, 4]})
test.show()
Out[92]:
In [93]:
choice(range(6))
Out[93]:
1
In [94]:
from random import choice
def AZI_max(graf, n=100, tol=10^-9, i=0, 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)
i += 1
K = Graph(graf)
if i > n:
return(AZIvrednost(K, alpha))
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 [97]:
B = generiranje_dreves(100)
AZI_max(B,10000, alpha = -10)
Out[97]:
Out[97]:
(Graph on 100 vertices, 46052604311303188647463921/18280792200314880000000000)
In [0]:
from random import choice
def AZI_min(graf, n=100, tol=10^-9, i=0, 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)
i += 1
K = Graph(graf)
if i > n:
return(AZIvrednost(K, alpha))
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 [98]:
B = generiranje_dreves(100)
AZI_min(B,10000, alpha = 10)
Out[98]:
Out[98]:
(Graph on 100 vertices, 2615117517349564772614520758236679811/114752696193360080142336000000000)
In [0]:
In [0]:
In [0]: