[SOLVED] Homework 5, part 2

Homework 5, part 2

Math 157: Intro to Mathematical Software
UC San Diego, Winter 2022

Copyright By Assignmentchef assignmentchef

Homework 5 (part 2 of 2): due Thursday, February 17 at 8PM Pacific

See part 1 for the usual instructions about collaborators and outside resources.

In this notebook, all computations should use the Julia 1.6 or Julia 1.7 kernel (it shouldnt matter which).

Problem 5: Counting spanning trees

Grading criteria: code correctness.

Recall that in Lecture 16, I demonstrated an example where I counted the number of spanning trees of a large graph; this was done using the Kirchhoff matrix tree theorem. The theorem can be stated as follows. Let $G$ be a graph with adjacency matrix $A$. Let $D$ be the diagonal vector whose entries are the degrees of the vertices of $G$. Then $D-A$ (which we saw already in problem 4) has determinant 0, and the number of spanning trees equals the absolute value of every cofactor of $A$ (i.e., the determinant of the matrix you get by excluding one row and column from $A$).

5a) (5 points) Write a function that, given a Julia graph $G$, computes the number of spanning trees using Kirchhoffs theorem. Check your work using the code cell below: the number of spanning trees of an $n$-cycle is exactly $n$.

using LightGraphs
using LinearAlgebra
function num_spanning_trees(G)
A = adjacency_matrix(G)
D = Diagonal([degree(G, i) for i in 1:G(0)])
B = Matrix(D-A)
C = det(B[2:end,2:end])

num_spanning_trees (generic function with 1 method)

G = Graph()
add_vertices!(G, 4)
for t in [(1,2), (2,3), (3,4), (4,1)]
add_edge!(G, t)
num_spanning_trees(G) == 4

MethodError: objects of type SimpleGraph{Int64} are not callable

Stacktrace:
[1] num_spanning_trees(G::SimpleGraph{Int64})
@ Main ./In[31]:5
[2] top-level scope
@ In[32]:6
@ ./boot.jl:373 [inlined]
[4] include_string(mapexpr::typeof(REPL.softscope), mod::Module, code::String, filename::String)
@ Base ./loading.jl:1196

5b) (2 points) Using your function in 5a), count the number of spanning trees of the Petersen graph. You can check your answer against SageMath by copying the code from the following raw cell into another notebook. (Hint: use code from Lecture 17 to create the Petersen graph in Julia.)

PG = graphs.PetersenGraph()
PG.spanning_trees_count()

## Your code goes here

5c) (3 points) The Petersen graph has a lot of symmetries (that is, it has a large automorphism group). Describe two spanning trees that are not related by any symmetry of the Petersen graph.

Hint: one way to ensure that two spanning trees are not related by any symmetry is to make them structurally different, e.g., one of them is a straight path and the other is not.

Answer box:

Problem 6: The principle behind PageRank

Grading criteria: code correctness for 6a and 6b; mathematical correctness for 6c.

In this problem, we work with this dataset of hyperlinks among 1224 blogs covering the US Presidential election of 2004. The datafile consists of a series of lines representing the two endpoints of an edge of a directed graph (have a look at it to see what I mean).

The principle at work here is the basis of the PageRank algorithm used by Google as part of its ranking of search engine results.

6a) (3 points) The following code block reads the lines of blogdata.txt into the vector lines. Convert this into the sparse matrix $A$ in which $A_{i,j}$ equals 1 if there is a directed edge from $i$ to $j$ and 0 otherwise.

Hint: use split(s, ) to split the string s at spaces, and parse(Int, s) to convert the string s into an integer.

using SparseArrays;
lines = readlines(blogdata.txt);
# Your code goes here

6b) (4 points) Find the eigenvector of A with the largest positive real eigenvalue (you may need to convert A into a dense matrix first), and check that it has nonnegative real entries.

Hint: convert A into a dense matrix to use LinearAlgebra.eigvals and LinearAlgebra.eigvecs. Remember that the latter gives you a matrix whose columns are eigenvectors of A.

## Your code goes here

6c) (3 points) Based on your answer to 6a), identify the five most influential blogs from this dataset. Explain your reasoning.

## Your code goes here

Answer box:

CS: assignmentchef QQ: 1823890830 Email: [email protected]