\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amssymb,amsfonts,fancyhdr,multicol,mathptmx,graphicx}
\usepackage{tikz}
\usetikzlibrary{arrows}

\renewcommand{\baselinestretch}{1.1}
\theoremstyle{plain}
\newtheorem*{theorem}{Theorem}
\newtheorem*{DMV}{Matrix Tree Theorem (Directed Multigraph Version)}
%\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{remark}{Remark}
\newtheorem*{example*}{Example}
\newtheorem*{definition*}{Definition}
\newcommand{\bp}{\begin{problem}}
\newcommand{\ep}{\end{problem}}

\newtheorem*{answer}{Answer}
\newtheorem*{lemma*}{Lemma}
\newtheorem*{theorem*}{Theorem}
\newcommand{\ba}{\begin{answer}}
\newcommand{\ea}{\end{answer}}

\newcommand{\ds}{\displaystyle}
\newcommand{\ben}{\renewcommand{\theenumi}{\alph{enumi}}\renewcommand{\labelenumi}{(\theenumi)}\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}

\newcommand{\Z}{\mathbb{Z}} 
\newcommand{\N}{\mathbb{N}} 
\newcommand{\R}{\mathbb{R}} 
\newcommand{\C}{\mathbb{C}} 



\fancyhead[L]{\Large \textbf{Math 634 Spring 2016}}
\fancyhead[R]{\large \textbf{Final Exam}}


\begin{document}
\pagestyle{fancy}
\fancyfoot[R,L,C]{}

\bp Consider the graph below as an electrical circuit where each edge has resistance $1$ and a current of size $1$ enters the graph at the source at the top and exits the graph at the sink at the bottom.

\begin{center}
\includegraphics{ElectricalCircuit.pdf}
\end{center}


\ben
\item Compute the number of spanning trees.  Do it several ways:  divide the product of the nonzero eigenvalues of the Laplacian by the number of vertices, compute the determinant of the reduced Laplacian, draw pictures of all of them.
\item Determine the current flowing in each edge by solving the equations in Kirchoff's laws.
\item Determine the current flowing in the dotted edge by Theorem 1 in Section II.1 in the book.  Your answer here will be a few pictures.
\item Compute the page ranks for the directed graph obtained by connecting the sink to the source and considering the edges to be directed according to the flow of the current.
\een
\ep

\bp For each of the following statements, decide whether it is true or false.  If the statement is true give a brief proof.  If it's false, give a counterexample.
\ben
\item If $3$ is an eigenvalue of the adjacency matrix of a graph, then the graph has a vertex of degree $3$.
\item The adjacency matrix of a bipartite graph with an odd number of vertices is singular.
\item Let $G$ be a graph.  For any $k=1, \ldots, \text{size}(G)$, let $L_k$ be the Laplacian of $G$ with the $k$-the row and $k$-th column removed.  Then $L_k$ is invertible if and only if $G$ is connected. 
\item Let $v=\begin{bmatrix}v_1\\ \vdots\\ v_n\end{bmatrix}$.  Suppose one entry of $v$ is $+1$, one entry is $-1$, and all the rest are zero.  Then $v$ is an eigenvector with eigenvalue $n$of the Laplacian of the complete graph $K_n.$  
\een
\ep

\bp \textbf{[Bonus]}
Consider the electrical network pictured below.  The weights on the edges are conductances.
\begin{center}
\includegraphics{WeightedGraph.pdf}
\end{center}
Use absolute voltage potentials $v_6=1$ and $v_4=0$ (red is the source, black is the sink) to solve for the absolute voltage potentials at every other vertex.  Determine the total current of the network.

You'll probably want to use a computer to solve the problem.  Here are some options, depending on your programming skills / appetite:


\begin{itemize}
\item Set up the equations by hand and ask a computer algebra system to solve the system.
\item Modify the class notes from May 12 to include variable conductance and solve the matrix equation corresponding to Kirchoff's current law.
\item Write a general program that inputs the adjacency matrix, weighted by conductance, of an electrical network and outputs the absolute voltage potentials and total current.
\item Program a computer to approximate the absolute voltage potentials and total current using random walks weighted by conductance as described in Theorem 8 in the book.  For this, you can also modify the class notes from May 12 to include variable conductance.
\end{itemize}

\ep

\end{document}

