Osnovni pojmovi iz teorije grafova u pythonu
In [1]:
import platform
In [2]:
platform.platform()
Out[2]:
In [3]:
platform.python_version()
Out[3]:
In [4]:
import networkx as nx
In [5]:
nx.__version__
Out[5]:
In [6]:
from pylab import *
In [7]:
%matplotlib inline
In [8]:
import DSTG
funkcija za ispitivanje regularnosti grafa
In [9]:
def is_regular(G):
vrhovi=list(G.nodes())
r=G.degree(vrhovi[0])
for v in vrhovi.__iter__():
if G.degree(v)!=r: return False
return True
Prazni graf
kreiranje praznog grafa s 8 vrhova (1. način)
In [10]:
G=nx.Graph()
G.add_nodes_from(range(1,9))
In [11]:
G
Out[11]:
kreiranje praznog grafa s 8 vrhova (2. način)
In [12]:
G1=nx.empty_graph(8)
In [13]:
G1
Out[13]:
broj vrhova u G
In [14]:
G.number_of_nodes()
Out[14]:
In [15]:
len(G)
Out[15]:
In [16]:
G.order()
Out[16]:
In [17]:
G.__len__()
Out[17]:
broj bridova u G
In [18]:
G.number_of_edges()
Out[18]:
In [19]:
G.size()
Out[19]:
crtanje grafa G
In [20]:
nx.draw(G,with_labels=True)
crtanje grafa G tako da su vrhovi poredani po kružnici
In [21]:
nx.draw_circular(G,with_labels=True)
crtanje grafa G s random rasporedom vrhova
In [22]:
nx.draw_random(G,with_labels=True)
Petersenov graf
In [23]:
P=nx.petersen_graph()
In [24]:
print(nx.info(P))
broj vrhova
In [25]:
P.number_of_nodes()
Out[25]:
broj bridova
In [26]:
P.number_of_edges()
Out[26]:
crtanje grafa
In [27]:
nx.draw(P,with_labels=True)
In [28]:
nx.draw_circular(P,with_labels=True)
In [29]:
nx.draw_random(P,with_labels=True)
In [30]:
nx.draw_spring(P,with_labels=True)
neke dodatne opcije za crtanje grafova (pogledajte help za više informacija)
In [31]:
nx.draw(P,node_size=400,node_color='y',node_shape='s',width=3,edge_color='r',with_labels=True)
Petersenov graf nacrtan s tipičnim razmještajem vrhova
In [32]:
figure(figsize=[7,7])
poz=nx.shell_layout(P,[[5,6,7,8,9],[0,1,2,3,4]])
nx.draw(P,pos=poz,with_labels=True)
vrhovi grafa P
In [33]:
P.nodes()
Out[33]:
bridovi grafa P
In [34]:
P.edges()
Out[34]:
stupnjevi vrhova u grafu P
In [35]:
P.degree()
Out[35]:
Petersonov graf je regularan
In [36]:
is_regular(P)
Out[36]:
komplement grafa P
In [37]:
figure(figsize=(6,4))
cP=nx.complement(P)
nx.draw_circular(cP,with_labels=True)
linijski graf od P
In [38]:
figure(figsize=(8,8))
lP=nx.line_graph(P)
nx.draw_circular(lP,node_size=800,font_size=10,with_labels=True)
matrica susjedstva grafa P
In [39]:
Pmatrica = nx.adj_matrix(P)
Pmatrica
Out[39]:
In [40]:
print(Pmatrica)
In [41]:
Pmatrica.todense()
Out[41]:
In [42]:
print(Pmatrica.todense())
In [43]:
nx.to_pandas_adjacency(P,dtype=int)
Out[43]:
lista susjedstva grafa P
In [44]:
P.adj
Out[44]:
In [45]:
P.adjacency()
Out[45]:
In [46]:
list(P.adjacency())
Out[46]:
matrica incidencije
incidence_matrix(G, nodelist=None, edgelist=None, oriented=False, weight=None)
In [47]:
Pincm = nx.incidence_matrix(P)
Pincm
Out[47]:
In [48]:
print(Pincm)
In [49]:
Pincm.todense()
Out[49]:
In [50]:
print(Pincm.todense())
Kubni graf
In [51]:
kubniGraf=nx.cubical_graph()
broj vrhova
In [52]:
kubniGraf.number_of_nodes()
Out[52]:
broj bridova
In [53]:
kubniGraf.number_of_edges()
Out[53]:
crtanje grafa
In [54]:
nx.draw(kubniGraf,with_labels=True)
vrhovi kubnog grafa
In [55]:
kubniGraf.nodes()
Out[55]:
In [56]:
list(kubniGraf.nodes())
Out[56]:
bridovi kubnog grafa
In [57]:
kubniGraf.edges()
Out[57]:
In [58]:
list(kubniGraf.edges())
Out[58]:
stupnjevi vrhova u kubnom grafu
In [59]:
kubniGraf.degree()
Out[59]:
In [60]:
dict(kubniGraf.degree())
Out[60]:
Kubni graf je regularan
In [61]:
is_regular(kubniGraf)
Out[61]:
komplement kubnog grafa
In [62]:
nx.draw(nx.complement(kubniGraf),with_labels=True)
linijski graf kubnog grafa
In [63]:
figure(figsize=(8,8))
nx.draw_circular(nx.line_graph(kubniGraf),node_size=800,font_size=10,with_labels=True)
vrhovi linijskog grafa od kubnog grafa
In [64]:
nx.line_graph(kubniGraf).nodes()
Out[64]:
In [65]:
list(nx.line_graph(kubniGraf).nodes())
Out[65]:
matrica susjedstva kubnog grafa
In [66]:
kG_mat = nx.adj_matrix(kubniGraf)
kG_mat
Out[66]:
In [67]:
print(kG_mat)
In [68]:
kG_mat.todense()
Out[68]:
In [69]:
print(kG_mat.todense())
In [70]:
nx.to_pandas_adjacency(kubniGraf,dtype=int)
Out[70]:
lista susjedstva kubnog grafa
In [71]:
kubniGraf.adj
Out[71]:
In [72]:
list(kubniGraf.adjacency())
Out[72]:
matrica incidencije
In [73]:
kG_inc = nx.incidence_matrix(kubniGraf)
kG_inc.todense()
Out[73]:
Potpuni graf
Potpuni graf $K_{10}$
In [74]:
K10=nx.complete_graph(10)
nx.draw_circular(K10,node_size=500,with_labels=True)
broj vrhova
In [75]:
K10.number_of_nodes()
Out[75]:
broj bridova
In [76]:
K10.number_of_edges()
Out[76]:
vrhovi potpunog grafa $K_{10}$
In [77]:
K10.nodes()
Out[77]:
bridovi potpunog grafa $K_{10}$
In [78]:
K10.edges()
Out[78]:
In [79]:
DSTG.ispis(K10.edges(),80)
stupnjevi vrhova
In [80]:
K10.degree()
Out[80]:
Graf $K_{10}$ je regularni.
In [81]:
is_regular(K10)
Out[81]:
komplement od $K_{10}$
In [82]:
figure(figsize=(6,4))
nx.draw(nx.complement(K10),with_labels=True)
linijski graf od $K_{10}$
In [83]:
figure(figsize=(12,8))
nx.draw_circular(nx.line_graph(K10),node_size=100,font_size=10)
matrica susjedstva od $K_{10}$
In [84]:
K10_mat = nx.adj_matrix(K10)
K10_mat
Out[84]:
In [85]:
print(K10_mat.todense())
In [86]:
nx.to_pandas_adjacency(K10,dtype=int)
Out[86]:
lista susjedstva od $K_{10}$
In [87]:
K10.adj
Out[87]:
In [88]:
list(K10.adjacency())
Out[88]:
matrica incidencije
In [89]:
K10_inc = nx.incidence_matrix(K10)
print(K10_inc.todense())
Potpuni graf $K_{25}$
In [90]:
figure(figsize=(8,8))
nx.draw_circular(nx.complete_graph(25),node_size=10)
Potpuni bipartitni graf
Potpuni bipartitni graf $K_{2,3}$
In [91]:
B23=nx.complete_bipartite_graph(2,3)
figure(figsize=(6,4))
nx.draw(B23,with_labels=True)
broj vrhova
In [92]:
B23.number_of_nodes()
Out[92]:
broj bridova
In [93]:
B23.number_of_edges()
Out[93]:
vrhovi poptunog bipartitnog grafa $K_{2,3}$
In [94]:
B23.nodes()
Out[94]:
bridovi potpunog bipartitnog grafa $K_{2,3}$
In [95]:
B23.edges()
Out[95]:
stupnjevi vrhova
In [96]:
B23.degree()
Out[96]:
Graf $K_{2,3}$ nije regularan.
In [97]:
is_regular(B23)
Out[97]:
komplement potpunog bipartitnog grafa $K_{2,3}$
In [98]:
nx.draw_circular(nx.complement(B23),with_labels=True)
linijski graf od $K_{2,3}$
In [99]:
nx.draw_circular(nx.line_graph(B23),node_size=800,font_size=10,with_labels=True)
matrica susjedstva od $K_{2,3}$
In [100]:
B23_mat = nx.adj_matrix(B23)
B23_mat
Out[100]:
In [101]:
print(B23_mat.todense())
In [102]:
nx.to_pandas_adjacency(B23,dtype=int)
Out[102]:
lista susjedstva od $K_{2,3}$
In [103]:
B23.adj
Out[103]:
In [104]:
list(B23.adjacency())
Out[104]:
matrica incidencije
In [105]:
B23_inc = nx.incidence_matrix(B23)
B23_inc
Out[105]:
In [106]:
print(B23_inc.todense())
$n$-dimenzionalna kocka
In [107]:
nx.draw(nx.hypercube_graph(3))
In [108]:
nx.draw(nx.hypercube_graph(4),node_size=50)
In [109]:
nx.draw(nx.hypercube_graph(5),node_size=50)
šminkanje grafa (kompliciranijih primjera ima na webu)
Uočite, ako niste zadovoljni niti jednim razmještajem vrhova koje networkx automatski izračuna, možete sami eksplicitno unijeti koordinate pojedinih vrhova kao rječnik pridružen varijabli "pos".
In [110]:
nx.draw(B23,pos={0:[2,1],1:[2,3],2:[0,0],3:[0,2],4:[0,4]},
node_color=[[1,0,0],[1,0,0],[0,0,1],[0,0,1],[0,0,1]],
node_size=[300,300,600,600,600],
edge_color=[[1,0,0],[1,0,0],[1,0,0],[0,0,1],[0,0,1],[0,1,0]],
labels={0:'A',1:'B',2:'C',3:'D',4:'E'})
inducirani podgraf
In [111]:
figure(figsize=(12,8))
subplot(121)
title("Petersenov graf",fontsize=16)
poz=nx.shell_layout(P,[[5,6,7,8,9],[0,1,2,3,4]])
nx.draw(nx.petersen_graph(),pos=poz,with_labels=True)
subplot(122)
title("Inducirani podgraf sa skupom vrhova {0,1,2,3,4}",fontsize=16)
nx.draw(nx.subgraph(nx.petersen_graph(),[0,1,2,3,4]),pos=poz,with_labels=True)
brisanje vrhova u grafu
In [112]:
figure(figsize=(12,8))
P=nx.petersen_graph()
poz=nx.shell_layout(P,[[5,6,7,8,9],[0,1,2,3,4]])
subplot(121)
title("Petersenov graf",fontsize=16)
nx.draw(P,pos=poz,with_labels=True)
subplot(122)
title("Petersenov graf bez vrhova 0,4,6,9",fontsize=16)
P.remove_nodes_from([0,4,6,9])
nx.draw(P,pos=poz,with_labels=True)
brisanje bridova u grafu
In [113]:
figure(figsize=(12,8))
P=nx.petersen_graph()
poz=nx.shell_layout(P,[[5,6,7,8,9],[0,1,2,3,4]])
subplot(121)
title("Petersenov graf",fontsize=16)
nx.draw(P,pos=poz,with_labels=True)
subplot(122)
title("Petersenov graf bez bridova (1,6),(7,9),(3,4),(0,5)",fontsize=16)
P.remove_edges_from([(1,6),(7,9),(3,4),(0,5)])
nx.draw(P,pos=poz,with_labels=True)
dodavanje vrhova, bridova i ciklusa u graf
In [114]:
figure(figsize=(15,8))
C6=nx.cycle_graph(6)
subplot(131)
title("Zadani graf",fontsize=16)
nx.draw_circular(C6,with_labels=True)
subplot(132)
title("Dodani vrhovi b,o,k i bridovi (b,o),(k,0)",fontsize=16)
C6.add_nodes_from('bok')
C6.add_edges_from([('b','o'),('k',0)])
nx.draw_circular(C6,with_labels=True)
subplot(133)
title("Dodan ciklus 0-o-5-0",fontsize=16)
C6.add_cycle([0,'o',5])
nx.draw_circular(C6,with_labels=True)
dodavanje puta u graf
In [115]:
figure(figsize=(12,8))
C8=nx.cycle_graph(8)
subplot(121)
title("Zadani graf",fontsize=16)
nx.draw_circular(C8,with_labels=True)
subplot(122)
title("Dodani put 1-3-5-7",fontsize=16)
C8.add_path([1,3,5,7])
nx.draw_circular(C8,with_labels=True)
dodavanje zvijezde u graf
In [116]:
figure(figsize=(12,8))
C8=nx.cycle_graph(8)
subplot(121)
title("Zadani graf",fontsize=16)
nx.draw_circular(C8,with_labels=True)
subplot(122)
title("Dodana zvijezda u graf",fontsize=16)
C8.add_star(['s',1,2,3,4,5,6,7])
poz2=nx.shell_layout(C8,[['s'],[0,1,2,3,4,5,6,7]])
nx.draw(C8,pos=poz2,with_labels=True)
unija grafova
(grafovi moraju imati disjunktne skupove vrhova)
1. način
In [117]:
G=nx.complete_graph(5)
H=nx.complete_bipartite_graph(2,3)
GuH=nx.union(G,H,rename=('g','h'))
figure(figsize=(15,8))
subplot(131)
title("G",fontsize=16)
nx.draw_circular(G,with_labels=True)
subplot(132)
title("H",fontsize=16)
nx.draw_circular(H,with_labels=True)
subplot(133)
title("Unija grafova G i H",fontsize=16)
nx.draw_circular(GuH,with_labels=True)
2. način
In [118]:
G=nx.complete_graph(5)
H=nx.complete_bipartite_graph(2,3)
GuH=nx.disjoint_union(G,H)
figure(figsize=(15,8))
subplot(131)
title("G",fontsize=16)
nx.draw_circular(G,with_labels=True)
subplot(132)
title("H",fontsize=16)
nx.draw_circular(H,with_labels=True)
subplot(133)
title("Unija grafova G i H",fontsize=16)
nx.draw_circular(GuH,with_labels=True)
presjek grafova
(grafovi moraju imati jednake skupove vrhova)
In [119]:
G=nx.complete_bipartite_graph(5,5)
H=nx.petersen_graph()
GintH=nx.intersection(G,H)
pozG=dict([(x,[x//5,x%5]) for x in G.nodes()])
pozH=nx.shell_layout(H,[[5,6,7,8,9],[0,1,2,3,4]])
figure(figsize=(15,8))
subplot(131)
title("G",fontsize=16)
nx.draw(G,pos=pozG,with_labels=True)
subplot(132)
title("H",fontsize=16)
nx.draw(H,pos=pozH,with_labels=True)
subplot(133)
title("Presjek grafova G i H",fontsize=16)
nx.draw_circular(GintH,with_labels=True)
kreiranje grafa iz matrice susjedstva
matrica susjedstva
In [120]:
A=matrix([[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]])
print(A)
kreiranje grafa iz matrice susjedstva
In [121]:
G=nx.from_numpy_matrix(A)
vrhovi grafa G
In [122]:
G.nodes()
Out[122]:
bridovi grafa G
In [123]:
list(G.edges())
Out[123]:
stupnjevi vrhova
In [124]:
G.degree()
Out[124]:
Uočite da se ne crtaju petlje. NetworkX nema napredne metode crtanja grafova. NetworkX je modul za napredani rad s grafovima, a pritom nudi neke metode za crtanje jednostavnih grafova (u kojima nema petlji i višestrukih bridova).
In [125]:
figure(figsize=(6,4))
nx.draw(G,with_labels=True)
Međutim, možemo NetworkX graf pretvoriti u GraphViz format. Pritom moramo imati instalirane python module za rad s GraphVizom. To su moduli pydot i pygraphviz.
In [126]:
G1=nx.nx_agraph.to_agraph(G)
GraphViz crta graf i sprema sliku u datoteku u radni direktorij. Varijabla "prog" može imati sljedeće vrijednosti: dot, neato, twopi, circo, fdp. Na temelju tih vrijednosti se određuje razmještaj vrhova.
In [127]:
G1.draw('Gd.png',prog='dot')
Želimo li nacrtanu sliku prikazati u Jupyter notebooku
In [128]:
from IPython.core.display import Image
In [129]:
Image(filename='Gd.png')
Out[129]:
GraphViz je moćan alat za crtanje grafova. Jasno, sada su nacrtane i petlje, a bridovi nisu nužno dužine, već i krivulje tako da sam prikaz grafa lijepo vizualno izgleda.
Crtanje grafa s GraphVizom tako da vrhovi budu raspoređeni na kružnici
In [130]:
G1.draw('Gc.png',prog='circo')
In [131]:
Image(filename='Gc.png')
Out[131]:
kreiranje grafa iz zadanog skupa bridova
In [132]:
bridovi=[(0,0),(0,1),(0,1),(0,3),(0,3),(0,4),(1,1),
(1,2),(1,2),(1,4),(2,2),(2,3),(2,3),(2,4),(3,3),(3,4)]
Moramo staviti opciju create_using=nx.MultiGraph() kako bi se uvažili višestruki bridovi
In [133]:
Z=nx.from_edgelist(bridovi,create_using=nx.MultiGraph())
In [134]:
list(Z.edges())
Out[134]:
In [135]:
Z.nodes()
Out[135]:
stupnjevi vrhova
In [136]:
Z.degree()
Out[136]:
ne crtaju se petlje i višestruki bridovi
In [137]:
nx.draw(Z,with_labels=True)
Problem opet efikasno rješavamo s GraphVizom.
In [138]:
Z1=nx.nx_agraph.to_agraph(Z)
In [139]:
Z1.draw('Z1.png',prog='circo')
In [140]:
Image(filename='Z1.png')
Out[140]:
izomorfizam grafova
In [141]:
A=matrix([[0,1,0,1,1],[1,0,1,0,0],[0,1,0,0,1],[1,0,0,0,0],[1,0,1,0,0]])
B=matrix([[0,1,0,0,1],[1,0,0,1,0],[0,0,0,1,0],[0,1,1,0,1],[1,0,0,1,0]])
G1=nx.from_numpy_matrix(A)
G2=nx.from_numpy_matrix(B)
In [142]:
print(A)
In [143]:
print(B)
In [144]:
figure(figsize=(8,6))
subplot(121)
title("Graf $G_1$",fontsize=16)
nx.draw(G1,with_labels=True)
subplot(122)
title("Graf $G_2$",fontsize=16)
nx.draw(G2,with_labels=True)
Grafovi $G_1$ i $G_2$ su izomorfni.
In [145]:
nx.is_isomorphic(G1,G2)
Out[145]:
Dobivanje izomorfizma
In [146]:
GM=nx.algorithms.isomorphism.GraphMatcher(G1,G2)
In [147]:
GM.is_isomorphic()
Out[147]:
In [148]:
nx.isomorphism.could_be_isomorphic(G1,G2)
Out[148]:
izomorfizam s $G_1$ na $G_2$
In [149]:
GM.mapping
Out[149]:
izomorfizam s $G_1$ na $G_2$
In [150]:
GM.core_1
Out[150]:
izomorfizam s $G_2$ na $G_1$
In [151]:
GM.core_2
Out[151]:
svi izomorfizmi između $G_1$ i $G_2$
In [152]:
for u in GM.isomorphisms_iter():
print(u)
Neki primjeri generiranja grafova na slučajni način
Neki graf s 15 vrhova i 30 bridova
In [153]:
R1=nx.gnm_random_graph(15,30)
nx.draw_circular(R1,with_labels=True)
Neki graf s 15 vrhova i 85 bridova
Naredba dense_gnm_random_graph je brža od naredbe gnm_random_graph ako generiramo gusti graf, tj. graf koji ima puno bridova s obzirom na broj vrhova.
In [154]:
R2=nx.dense_gnm_random_graph(15,85)
nx.draw_circular(R2,with_labels=True)
Jednostavni graf s $15$ vrhova može imati najviše $\binom{15}{2}=105$ bridova. Ako napišete više bridova, generirat će se samo potpuni graf s $15$ vrhova.
In [155]:
R3=nx.dense_gnm_random_graph(15,120)
In [156]:
R3.number_of_edges()
Out[156]:
Slučajni graf s 15 vrhova i vjerojatnošću 0.3 da se kreira brid.
In [157]:
R4=nx.gnp_random_graph(15,0.3)
nx.draw_circular(R4,with_labels=True)
Veća vjerojatnost kreiranja brida daje gušći graf.
In [158]:
R5=nx.gnp_random_graph(15,0.8)
nx.draw_circular(R5,with_labels=True)
fast_gnp_random_graph bi trebao biti brži od gnp_random_graph kada je vjerojatnost kreiranja brida mala i kada je očekivani broj bridova mali.
In [159]:
R6=nx.fast_gnp_random_graph(15,0.3)
nx.draw_circular(R6,with_labels=True)
Neki 4-regularni graf s 15 vrhova
In [160]:
R7=nx.random_regular_graph(4,15)
nx.draw_circular(R7,with_labels=True)
Neki bipartitni graf s 5 vrhova u prvom članu biparticije, 3 vrha u drugom članu biparticije i ukupno 12 bridova.
In [161]:
B1=nx.algorithms.bipartite.gnmk_random_graph(5,3,12)
B1a=nx.nx_agraph.to_agraph(B1)
In [162]:
B1a.draw('B1.png',prog='dot')
In [163]:
Image(filename='B1.png')
Out[163]:
Neki bipartitni graf s 5 vrhova u prvom članu biparticije, 3 vrha u drugom članu biparticije i vjerojatnošću 0.3 da se kreira brid.
In [164]:
B2=nx.algorithms.bipartite.random_graph(5,3,0.3)
B2a=nx.nx_agraph.to_agraph(B2)
In [165]:
B2a.draw('B2.png',prog='dot')
In [166]:
Image(filename='B2.png')
Out[166]:
niz stupnjeva vrhova
Jednostavni graf s nizom stupnjeva vrhova $4,3,3,2,2$
In [167]:
S1=nx.havel_hakimi_graph([4,3,3,2,2])
In [168]:
nx.draw_circular(S1,with_labels=True)
slučajni jednostavni graf s nizom stupnjeva vrhova $4,3,3,2,2$
In [169]:
S2=nx.random_degree_sequence_graph([4,3,3,2,2])
In [170]:
nx.draw_circular(S2,with_labels=True)
Ne postoji jednostavni graf s nizom stupnjeva vrhova $1,2,3,4,4$
In [171]:
nx.is_graphical([1,2,3,4,4])
Out[171]:
No, postoji graf s nizom stupnjeva vrhova $1,2,3,4,4$. Jasno, taj graf nije jednostavan. Dolje je naveden samo jedan takav primjer grafa koji je kreiran na slučajni način.
In [172]:
S3=nx.configuration_model([1,2,3,4,4])
In [173]:
S3a=nx.nx_agraph.to_agraph(S3)
S3a.draw('S3.png',prog='circo')
In [174]:
Image(filename='S3.png')
Out[174]:
Bipartitni graf sa zadanim nizovima stupnjeva vrhova po pojedinim biparticijama. Pazite, sume stupnjeva vrhova u obje biparticije moraju biti jednake da bi takav graf postojao.
In [175]:
S4=nx.algorithms.bipartite.havel_hakimi_graph([3,4,2,1],[2,3,3,2])
In [176]:
S4a=nx.nx_agraph.to_agraph(S4)
S4a.draw('S4.png',prog='dot')
In [177]:
Image(filename='S4.png')
Out[177]:
In [178]:
S5=nx.algorithms.bipartite.configuration_model([3,4,2,1],[8,2])
In [179]:
S5a=nx.nx_agraph.to_agraph(S5)
S5a.draw('S5.png',prog='dot')
In [180]:
Image(filename='S5.png')
Out[180]:
Atlas grafova
Skup svih jednostavnih neizomorfnih grafova s najviše 7 vrhova
In [181]:
skup_grafova=nx.graph_atlas_g()
Ukupno postoje 4 neizomorfna jednostavna grafa s 3 vrha.
In [182]:
graf_3vrha=[]
for g in skup_grafova.__iter__():
if g.number_of_nodes()>3: break
if g.number_of_nodes()==3:
graf_3vrha.append(g)
In [183]:
len(graf_3vrha)
Out[183]:
Svi neizomorfni jednostavni grafovi s 3 vrha
In [184]:
for i in range(1,5):
subplot(2,2,i,xticks=[], yticks=[])
nx.draw_circular(graf_3vrha[i-1],with_labels=True)
axis('on')
margins(x=0.1,y=0.1)
Ukupno postoji 11 neizomorfnih jednostavnih grafova s 4 vrha.
In [185]:
graf_4vrha=[]
for g in skup_grafova.__iter__():
if g.number_of_nodes()>4: break
if g.number_of_nodes()==4:
graf_4vrha.append(g)
In [186]:
len(graf_4vrha)
Out[186]:
Svi neizomorfni jednostavni grafovi s 11 vrhova
In [187]:
figure(figsize=(6,6))
for i in range(1,12):
subplot(4,3,i,xticks=[], yticks=[])
nx.draw_circular(graf_4vrha[i-1],with_labels=True)
axis('on')
margins(x=0.15,y=0.17)
Ukupno postoji 34 neizomorfnih jednostavnih grafova s 5 vrhova.
In [188]:
graf_5vrha=[]
for g in skup_grafova.__iter__():
if g.number_of_nodes()>5: break
if g.number_of_nodes()==5:
graf_5vrha.append(g)
In [189]:
len(graf_5vrha)
Out[189]:
In [190]:
figure(figsize=(8,8))
for i in range(1,35):
subplot(6,6,i,xticks=[], yticks=[])
nx.draw_circular(graf_5vrha[i-1],node_size=50)
axis('on')
margins(x=0.1,y=0.1)
In [ ]: