Übungsblatt_6
WS 2010/11
BEISPIEL 17
Schreiben Sie einen Algorithmus der feststellt ob ein gegebener Graph G bipartit ist.
Demonstrieren Sie den Algorithmus anhand eines "zufälligen" Graphen mit mindestens 15 Knoten bzw. einem bipartiten Graphen mit mindestens 10 Knoten.
WS 2010/11
BEISPIEL 17
Schreiben Sie einen Algorithmus der feststellt ob ein gegebener Graph G bipartit ist.
Demonstrieren Sie den Algorithmus anhand eines "zufälligen" Graphen mit mindestens 15 Knoten bzw. einem bipartiten Graphen mit mindestens 10 Knoten.
G=Graph({3:[6,4,2],1:[7,0,2,9],6:[8,5]})
H=graphs.RandomGNP(15,random())
def bipartite(G):
for s in [x[0] for x in G.connected_components()]:
aviable=[s]
color={s:True}; #color True or False
while len(aviable):
act=aviable.pop(0)
for n in G.neighbors(act):
if n not in color:
color[n]=not color[act]
aviable+=[n]
elif color[n]==color[act]:
return false
return True
li=[plot(G)+text("G, bipartite: "+str(bipartite(G)),(-0.8,1)),
plot(H)+text("H, bipartite: "+str(bipartite(H)),(-0.8,1))]
show(animate(li,xmin=-1,ymin=-1,xmax=1,ymax=1,axes=false),delay=200) #alternative: show(li[0]);show(li[1])
|
BEISPIEL 18
Schreiben Sie einen Algorithmus, der den größten vollständigen Teilgraphen in einem Graphen G findet.
Demonstrieren Sie den Algorithmus anhand eines "zufälligen" Graphen mit mindestens 15 Knoten.
def bron(G,R,P,X): #at wiki: "Bron–Kerbosch algorithm"
if len(P)==0*len(X)==0:
return [R]
cliq=[]
for k in P:
for cl in bron(G,R+Set([k]),P.intersection(Set(G.neighbors(k))),X.intersection(Set(G.neighbors(k)))):
cliq+=[cl]
P-=Set([k]); X+=Set([k])
return cliq
max(bron(H,Set([]),Set(H.vertices()),Set([])),key=lambda s:len(s))
{0, 2, 4, 6, 8, 9}
{0, 2, 4, 6, 8, 9}
|
BEISPIEL 19
Gegeben sei ein Graph G und ein Knoten x von G. Schreiben Sie einen Algorithmus der feststellt ob x Teil eines Kreises in G ist.
Demonstrieren Sie den Algorithmus anhand eines "zufälligen" Graphen mit mindestens 15 Knoten.
def path(g,a,b,vis): #oneliner too slow..
if a==b:
return true
vis+=[a]
for x in g.neighbors(a):
if x not in vis and path(g,x,b,vis):
return true
return false
def inCircle(G,x):
return true in [path(G.subgraph(edges=list(Set(G.edges(labels=False))
-Set([(x,n),(n,x)]))),n,x,[]) for n in G.neighbors(x)]
[inCircle(H,i) for i in H.vertices()]
[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True] [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True] |