e07_graphs_and_random_graphs.sagews

#use Graph(n) to construct a grapn with n vertices
Graph(5)

Graph on 5 vertices

g = Graph(5)

#use the show method to get a picture of g
g.show()

g.add_edge(0,2)
g.add_edge(1,3)
g.add_edge(1,4)

g.show()

g.order()

5

g.size()

3

#there are many built-in famous graphs, accessible from the "graphs" class using methods of that class

pete = graphs.PetersenGraph()

pete.show()

pete.order()

10

pete.size()

15

#random() outputs numbers between 0 and 1
random()

0.08559033691177864

def weighted_flip():
    if random() <= 0.75:
        return 1 #heads!
    else:
        return 0 #tails!

weighted_flip()

1

[weighted_flip() for i in [1..10]]

[1, 1, 1, 1, 0, 0, 1, 1, 1, 1]

gunnar = graphs.BrinkmannGraph()

gunnar.show()

k5 = graphs.CompleteGraph(5)

latex(k5)

\begin{tikzpicture} \definecolor{cv0}{rgb}{0.0,0.0,0.0} \definecolor{cfv0}{rgb}{1.0,1.0,1.0} \definecolor{clv0}{rgb}{0.0,0.0,0.0} \definecolor{cv1}{rgb}{0.0,0.0,0.0} \definecolor{cfv1}{rgb}{1.0,1.0,1.0} \definecolor{clv1}{rgb}{0.0,0.0,0.0} \definecolor{cv2}{rgb}{0.0,0.0,0.0} \definecolor{cfv2}{rgb}{1.0,1.0,1.0} \definecolor{clv2}{rgb}{0.0,0.0,0.0} \definecolor{cv3}{rgb}{0.0,0.0,0.0} \definecolor{cfv3}{rgb}{1.0,1.0,1.0} \definecolor{clv3}{rgb}{0.0,0.0,0.0} \definecolor{cv4}{rgb}{0.0,0.0,0.0} \definecolor{cfv4}{rgb}{1.0,1.0,1.0} \definecolor{clv4}{rgb}{0.0,0.0,0.0} \definecolor{cv0v1}{rgb}{0.0,0.0,0.0} \definecolor{cv0v2}{rgb}{0.0,0.0,0.0} \definecolor{cv0v3}{rgb}{0.0,0.0,0.0} \definecolor{cv0v4}{rgb}{0.0,0.0,0.0} \definecolor{cv1v2}{rgb}{0.0,0.0,0.0} \definecolor{cv1v3}{rgb}{0.0,0.0,0.0} \definecolor{cv1v4}{rgb}{0.0,0.0,0.0} \definecolor{cv2v3}{rgb}{0.0,0.0,0.0} \definecolor{cv2v4}{rgb}{0.0,0.0,0.0} \definecolor{cv3v4}{rgb}{0.0,0.0,0.0} % \Vertex[style={minimum size=1.0cm,draw=cv0,fill=cfv0,text=clv0,shape=circle},LabelOut=false,L=\hbox{$0$},x=2.5cm,y=5.0cm]{v0} \Vertex[style={minimum size=1.0cm,draw=cv1,fill=cfv1,text=clv1,shape=circle},LabelOut=false,L=\hbox{$1$},x=0.0cm,y=3.0902cm]{v1} \Vertex[style={minimum size=1.0cm,draw=cv2,fill=cfv2,text=clv2,shape=circle},LabelOut=false,L=\hbox{$2$},x=0.9549cm,y=0.0cm]{v2} \Vertex[style={minimum size=1.0cm,draw=cv3,fill=cfv3,text=clv3,shape=circle},LabelOut=false,L=\hbox{$3$},x=4.0451cm,y=0.0cm]{v3} \Vertex[style={minimum size=1.0cm,draw=cv4,fill=cfv4,text=clv4,shape=circle},LabelOut=false,L=\hbox{$4$},x=5.0cm,y=3.0902cm]{v4} % \Edge[lw=0.1cm,style={color=cv0v1,},](v0)(v1) \Edge[lw=0.1cm,style={color=cv0v2,},](v0)(v2) \Edge[lw=0.1cm,style={color=cv0v3,},](v0)(v3) \Edge[lw=0.1cm,style={color=cv0v4,},](v0)(v4) \Edge[lw=0.1cm,style={color=cv1v2,},](v1)(v2) \Edge[lw=0.1cm,style={color=cv1v3,},](v1)(v3) \Edge[lw=0.1cm,style={color=cv1v4,},](v1)(v4) \Edge[lw=0.1cm,style={color=cv2v3,},](v2)(v3) \Edge[lw=0.1cm,style={color=cv2v4,},](v2)(v4) \Edge[lw=0.1cm,style={color=cv3v4,},](v3)(v4) % \end{tikzpicture}

k5.show()

k100 = graphs.CompleteGraph(100)

k100.show()

k20 = graphs.CompleteGraph(20)

k20.show()

range(3)

[0, 1, 2]

g=Graph(3)
#3 possible edges
#we'll flip a coin by using randint(0,1) and calling 1 heads
for i in range(3):
    for j in range(3):
        if i < j:
            if randint(0,1) == 1:
                g.add_edge(i,j)
g.show()
print "g is connected = {}".format(g.is_connected())

g is connected = False

g.is_connected()

True

experiments = 1000
successes = 0
for i in [1..experiments]:
    g=Graph(3)
    #3 possible edges
    #we'll flip a coin by using randint(0,1) and calling 1 heads
    for i in range(3):
        for j in range(3):
            if i < j:
                if randint(0,1) == 1:
                    g.add_edge(i,j)

    if g.is_connected():
        successes = successes + 1
print n(successes/experiments)

0.512000000000000

#now we'd like to make our order=3 code work for random graphs with
#any order n
n = 100
experiments = 1000
successes = 0
for i in [1..experiments]:
    g=Graph(n)
    #3 possible edges
    #we'll flip a coin by using randint(0,1) and calling 1 heads
    for i in range(n):
        for j in range(n):
            if i < j:
                if randint(0,1) == 1:
                    g.add_edge(i,j)

    if g.is_connected():
        successes = successes + 1
print numerical_approx(successes/experiments)

1.00000000000000

area=100

area*1.0

100.000000000000

7/27.n()

0.259259259259259

#now we'd like to make our order=3 code work for random graphs with
#any order n
#and any edge probability p
p = 1/3
n = 3
experiments = 1000
successes = 0
for i in [1..experiments]:
    g=Graph(n)
    #3 possible edges
    #we'll flip a coin by using randint(0,1) and calling 1 heads
    for i in range(n):
        for j in range(n):
            if i < j:
                if random() < p:
                    g.add_edge(i,j)

    if g.is_connected():
        successes = successes + 1
print numerical_approx(successes/experiments)

0.246000000000000

#Questions: what's the depence of the probability that a random is connected on the order n and edge probability p
#to do: investigate how this probability varies with n and p
#Q1. fix p = 1/2 and investigate how the probability varies with n
#Q2. fix n and  investigate how the probability varies with p
def random_graph_connectedness(n,p, experiments):
    successes = 0
    for i in [1..experiments]:
        g=Graph(n)

        for i in range(n):
            for j in range(n):
                if i < j:
                    if random() < p:
                        g.add_edge(i,j)

        if g.is_connected():
            successes = successes + 1

    return (successes/experiments).n() #proportion of tested graphs that are connected

random_graph_connectedness(3,.5,10000)

0.501400000000000

#note: random_graph_connectness isn't a continuous function
#we'll scatter_plot instead
scatter_plot([(n,random_graph_connectedness(n,0.5,100)) for n in [3..100]])

#we'll scatter_plot instead
scatter_plot([(n,random_graph_connectedness(n,0.5,10000)) for n in [3..15]])

scatter_plot([(p,random_graph_connectedness(100,p,100)) for p in [.1*k for k in [0..10]]])

scatter_plot([(p,random_graph_connectedness(100,p,100)) for p in [.01*k for k in [0..20]]])

scatter_plot([(p,random_graph_connectedness(100,p,100)) for p in [.001*k for k in [0..200]]])

g = graphs.PetersenGraph()

g.show()

g.degree()

[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

min([5,4,6])

4

min(g.degree())

3

def min_degree(g):
    return min(g.degree())

g

Petersen graph: Graph on 10 vertices

min_degree(g)

3

def is_dirac(g):
    return min_degree(g) >= g.order()/2

g=graphs.PetersenGraph()

g.degree()

[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

show(g)

d3-based renderer not yet implemented

min_degree(g)

3

is_dirac(g)

False

def random_graph_dirac(n,p, experiments):
    successes = 0
    for i in [1..experiments]:
        g=Graph(n)

        for i in range(n):
            for j in range(n):
                if i < j:
                    if random() < p:
                        g.add_edge(i,j)

        if is_dirac(g):
            successes = successes + 1

    return (successes/experiments).n() #proportion of tested graphs that are connected

#checking the case where the order n = 3, and edge probability p = 1/2
#we know the analytic truth is .125
random_graph_dirac(3, 0.5, 1000)

0.141000000000000

n(8/27)

0.296296296296296

#what's the (empirical/experimental) probability that an order 3 graph ewith edge probability p = 2/3 is dirac
#the analytic truth is 8/27 = .296
random_graph_dirac(3, 2/3, 10000000)

0.296381200000000

#now we'd like to make our order=3 code work for random graphs with
#any order n
#and any edge probability p
p = 1/4
n = 20
experiments = 1000
successes = 0
for i in [1..experiments]:
    g=Graph(n)
    #3 possible edges
    #we'll flip a coin by using randint(0,1) and calling 1 heads
    for i in range(n):
        for j in range(n):
            if i < j:
                if random() < p:
                    g.add_edge(i,j)

    if g.is_connected():
        successes = successes + 1
print numerical_approx(successes/experiments)

0.915000000000000

def min_degree(g):
    return min(g.degree())

def is_dirac(g):
    return min_degree(g) >= g.order()/2

def random_graph_dirac(n,p, experiments):
    successes = 0
    for i in [1..experiments]:
        g=Graph(n)

        for i in range(n):
            for j in range(n):
                if i < j:
                    if random() < p:
                        g.add_edge(i,j)

        if is_dirac(g):
            successes = successes + 1

    return (successes/experiments).n() #proportion of tested graphs that are dirac

#random_graph_dirac()

scatter_plot([(n,random_graph_dirac(n,0.75,100)) for n in [2..100]])

average([2,3,4])

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 995, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> NameError: name 'average' is not defined

av