\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\setlength{\headheight}{0pt}
\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
        \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年12月9日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows, positioning}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\definecolor{mygray}{rgb}{0.4,0.4,0.4}
\definecolor{mygreen}{rgb}{0,0.8,0.6}
\definecolor{myorange}{rgb}{1.0,0.4,0}

\lstset{
    basicstyle=\footnotesize\sffamily\color{black},
    basicstyle=\tt,
    keywordstyle=\color{purple}\bfseries,
    commentstyle=\color{mygray},
    numbers=left,
    numbersep=5pt,
    numberstyle=\tiny\color{mygray},
    showspaces=false,
    showstringspaces=false,
    stringstyle=\color{myorange},
    tabsize=2,
    backgroundcolor=\color[RGB]{245,245,244}
}

\begin{document}

\textbf{Q1.}

(1.1)
\begin{proof}

    对 $\varphi(s,v)$ 归纳，$\varphi(s,v)=1$ 时是平凡的情况，此时
    $v=s$，不需循环即可确定.当 $\varphi(s,v)=2$ 时，$v$ 是 $s$ 相
    邻节点，且从 $s$ 到 $v$ 的最短路径即为 $(s,v)$ 这条边，因此在第
    一轮循环中，将 $s$ 从队列 $Q$ 中出队，便会在接下来的遍历 $s$ 相
    邻节点时确定下从 $s$ 到 $v$ 的最短路径长度，成立.

    假设 $\varphi(s,v)=n$ 时，从 $s$ 到 $v$ 的最短路径长度在第 $n-1$
    轮确定，以下证明在 $\varphi(s,v)=n+1$ 时，从 $s$ 到 $v$ 的最短
    路径长度会在第 $n$ 轮确定.

    第一轮循环中出队的只有起始节点 $s$，而之后的每轮循环中每个节点最
    多入队一次，而每个节点只有在还没确定下从 $s$ 到该节点最短路径长
    度时才会被入队.而因为使用队列，所以是一种广度优先搜索，在第 $n$
    轮循环中，所有从 $s$ 出发且路径上包括 $n+1$ 个节点才能到达的，且
    还未确定最短路径的节点，都会被入队，且同时进行松弛.因为前 $n-1$
    轮已经确定了路径包括 $n$ 个节点到达的节点的最短路径长度，所以在
    第 $n$ 轮循环中，可以确定下路径包括 $n+1$ 个节点到达的节点的最短
    路径长度，成立.

\end{proof}

(1.2)

\begin{figure}[h]
    \centering
    \begin{tikzpicture}[->,>=stealth]
        \node[draw, circle] (1) {1};
        \node[draw, circle] (2) [above=of 1] {2};
        \node[draw, circle] (3) [above left=of 1, yshift=-0.5cm] {3};
        \node[draw, circle] (4) [below left=of 1, yshift=0.5cm] {4};
        \node[draw, circle] (5) [below=of 1] {5};
        \node[draw, circle] (6) [below right=of 1, yshift=0.5cm] {6};
        \node[draw, circle] (7) [above right=of 1, yshift=-0.5cm] {7};

        \draw[->] (1) edge node {1} (7)
        edge node {3} (6)
        edge node {5} (5)
        edge node {7} (4)
        edge node {9} (3)
        edge node {11} (2)
        (7) edge node [right] {1} (6)
        (6) edge node {1} (5)
        (5) edge node {1} (4)
        (4) edge node [left] {1} (3)
        (3) edge node {1} (2);

    \end{tikzpicture}
\end{figure}

如图，节点 2 会在每一轮入队，时间复杂度达到 $\Omega(nm)$.

因此，$G_{n,m}$ 只需满足从顶点 1 到剩余 $n-1$ 个顶点间均有边，且
边 $(1,i)$ 权为 $2(n-i)+1$，同时 $\forall i>3$ 顶点 $i$ 到顶点
$i-1$ 间有边，权为 $1$ 即可.

(2.1)

在原始 Dijkstra 算法中，默认每次从未被确定最短路径的节点中选择的最
小权点就已经找到最短路径了，不再考虑可以先经过其他节点再走负权边到
达该节点的可能路径，因而不能处理负权边.而算法 2 中，即使是已经被加
入到 $S$ 也就是结果集合中的节点，如果它能被后面的某个节点松弛，仍
会对其进行处理，并将其从结果集合取出加回未完成处理的集合中，因此
算法 2 可以处理非正权边的图.

(2.2)

\begin{figure}[h]
    \centering
    \begin{tikzpicture}[->,>=stealth]
        \node[draw, circle] (1) {1};
        \node[draw, circle] (2) [right=2cm of 1] {2};
        \node[draw, circle] (3) [below right=of 1] {3};
        \node[draw, circle] (4) [right=2cm of 2] {4};
        \node[draw, circle] (5) [below right=of 2] {5};
        \node[draw, circle] (6) [right=2cm of 4] {6};
        \node[draw, circle] (7) [below right=of 4] {7};

        \draw[->] (1) edge node {1} (2)
        edge node {2} (3)
        (2) edge node {1} (4)
        edge node {2} (5)
        (3) edge node {-2} (2)
        (4) edge node {1} (6)
        edge node {2} (7)
        (5) edge node {-2} (4)
        (7) edge node {-2} (6);
    \end{tikzpicture}
\end{figure}

如图，每次都会在下方节点作为最小权点被取出后回溯上方已经选过的节点，因此时间复杂度较差.

因此构造 $G_n$ 中有 $2n+1$ 个节点，重复如图上这样的边权即可.

\textbf{Q2.}

以下节点上为\ 序号, (dfn, low).

(1.1)

见图~\ref{fig:2.1.1}

\begin{figure}[h]
    \centering
    \begin{tikzpicture}[->,>=stealth]
        \node[draw, circle] (1) at (0,0) {1,(1,1)};
        \node[draw, circle] (2) at (-3,3) {2,(2,1)};
        \node[draw, circle] (3) at (3,3) {3,(5,1)};
        \node[draw, circle] (4) at (9,3) {4,(6,6)};
        \node[draw, circle] (5) at (9,-3) {5,(9,9)};
        \node[draw, circle] (6) at (6,0) {6,(7,1)};
        \node[draw, circle] (7) at (3,-3) {7,(8,7)};
        \node[draw, circle] (8) at (-3,-3) {8,(4,1)};
        \node[draw, circle] (9) at (-3,0) {9,(3,1)};

        \draw[->] (1) edge node {树边} (2)
        edge node {树边} (3)
        edge node {树边} (7)
        edge node {前向边} (9)
        (2) edge node {树边} (9)
        (3) edge node {树边} (4)
        edge node {树边} (6)
        (5) edge node {横向边} (4)
        (6) edge node {后向边} (1)
        (7) edge node {横向边} (6)
        (8) edge node {后向边} (1)
        (9) edge node {树边} (8);
    \end{tikzpicture}
    \caption{Q2.1.1}\label{fig:2.1.1}
\end{figure}

强连通分量为 $V_1=\{1,2,3,6,7,8,9\}$ 和 $V_2=\{4\}$ 和 $V_3=\{5\}$，有向无环图表示为

\begin{figure}[h]
    \centering
    \begin{tikzpicture}[->,>=stealth]
        \node[draw, circle] (1) at (0,0) {$V_1$};
        \node[draw, circle] (2) at (3,0) {$V_2$};
        \node[draw, circle] (3) at (6,0) {$V_3$};
        \draw[->] (1) edge node {} (2)
        (3) edge node {} (2);
    \end{tikzpicture}
\end{figure}

(1.2)见图~\ref{fig:2.1.2}

\begin{figure}[ht]
    \centering
    \begin{tikzpicture}
        \node[draw, circle] (1) at (0,0) {1,(1,1)};
        \node[draw, circle] (2) at (-3,3) {2,(2,1)};
        \node[draw, circle] (3) at (3,3) {3,(5,1)};
        \node[draw, circle] (4) at (9,3) {4,(6,6)};
        \node[draw, circle] (5) at (9,-3) {5,(7,7)};
        \node[draw, circle] (6) at (6,0) {6,(8,1)};
        \node[draw, circle] (7) at (3,-3) {7,(9,1)};
        \node[draw, circle] (8) at (-3,-3) {8,(4,1)};
        \node[draw, circle] (9) at (-3,0) {9,(3,1)};

        \draw (1) edge node {前/后向边} (6)
        edge node {前/后向边} (7)
        edge node {前/后向边} (8)
        edge node {前/后向边} (9);
        \draw[->] (1) edge node {树边} (2)
        edge node {树边} (3)
        (2) edge node {树边} (9)
        (3) edge node {树边} (4)
        edge node {树边} (6)
        (4) edge node {树边} (5)
        (6) edge node {树边} (7)
        (9) edge node {树边} (8);
    \end{tikzpicture}
    \caption{Q2.1.2}\label{fig:2.1.2}
\end{figure}

其中割点有 $1,3,4$，桥有 $(3,4),(4,5)$

(2)

见算法~\ref{algo:2}

\begin{algorithm}[ht]
    \caption{计算所有节点的 low 值}\label{algo:2}
    \KwIn{图 $G=(V,E)$，其中以 $s$ 为起始节点}
    \KwOut{low 数组，内含每个顶点对应的 low 值}

    \SetKwProg{Fn}{Function}{:}{end}
    \SetKwFunction{Se}{Search-Low}
    dfncnt $\leftarrow$ 0\;
    init empty stack $S$\;
    \Se(s)\;

    \Fn{\Se{$v$}}{
    visited[$v$] $\leftarrow$ true\;
    low[$v$] $\leftarrow$ dfn[$v$] $\leftarrow$ ++dfncnt\;
    push $v$ into $S$\;
    inStack[$v$] $\leftarrow$ true\;
    \For{$(v,u)\in E$} {
        \uIf{${\rm !visited}[u]$} {
            \Se{$u$}\;
            low[$v$] $\leftarrow$ min (low[$v$], low[$u$])\;
        }
        \ElseIf{${\rm inStack}[u]$} {
            low[$v$] $\leftarrow$ min (low[$v$], dfn[$u$])\;
        }
    }
    \If{${\rm low}[v] \leftarrow {\rm dfn}[v]$} {
    \While{$S\ {\rm is\ not\ empty}$} {
    $u$ $\leftarrow$ pop $S$\;
    inStack[$u$] $\leftarrow$ false\;
    \If{$u=v$} {
        break\;
    }
    }
    }
    }

\end{algorithm}

(3.1)

只需在求 low 数组算法中当 $low[v]==dfn[v]$ 时，将栈中节点出栈到最后
一个出栈节点为 $v$，这一系列出栈节点都视为在要给强连通分量中.

(3.2)

如果在深度优先搜索树中一个非起始节点 $v$ 的子节点 $u$ 满足
low[$u$] $\geqslant$ dfn[$v$]，则 $v$ 是割点；若 $v$ 是起始节点，
则如果 $v$ 有多于一个子节点，$v$ 是割点；否则 $v$ 不是割点.

(3.3)

如果在深度优先搜索树中，某个节点 $v$ 的子节点 $u$ 满足
low[$u$] > dfn[$v$]，则边 $(v,u)$ 是桥.

\newpage

\textbf{Q3.}

(1) 见算法~\ref{algo:3}，分析最坏时间复杂度为 $O(|V|^3)$.

\begin{algorithm}[ht]
    \caption{求有向图中的全局最小环}\label{algo:3}
    \KwIn{有向图 $G=(V,E)$ 的邻接矩阵 $A[1..n][1..n]$，$n=|V|$}
    \KwOut{最小环 $ansPath$ 及最小环的边权和 $ans$}

    Init Matrix $dis[1..n][1..n]$\; Init Matrix $path[1..n][1..n]$\;
    $ans\leftarrow\infty$\; $anspath\leftarrow\varnothing$\; \For{$i\leftarrow 1$
        \KwTo$n$}{ \For{$j\leftarrow 1$ \KwTo$n$}{ \eIf{$A[i][j]\neq0$}{ $dis[i][j]
                    \leftarrow A[i][j]$\; $path[i][j]\leftarrow(i,j)$\; }{
                $dis[i][j]\leftarrow\infty$\; $path[i][j]\leftarrow\varnothing$\;} } }
    \For{$k\leftarrow 1$ \KwTo$n$}{ \For{$i\leftarrow 1$ \KwTo$k-1$}{
    \For{$j\leftarrow 1$ \KwTo$i-1$}{ \If{$dis[i][j]+A[i][k]+A[k][j]<ans$}{
    $ans\leftarrow A[i][k]+A[k][j]+dis[j][i]$\; $ansPath\leftarrow
        (i,k)\bigcup(k,j)\bigcup path[j][i]$\; } } } \For{$i\leftarrow 1$ \KwTo$n$}{
    \For{$j\leftarrow 1$ \KwTo$n$}{ \If{$dis[i][k]+dis[k][j]<dis[i][j]$}{
    $dis[i][j]\leftarrow dis[i][k]+dis[k][j]$\; $path[i][j]\leftarrow
        path[i][k]\bigcup path[k][j]$\; } } } }

\end{algorithm}

(2.1) 见算法~\ref{algo:3.2}，注意因为 $\textsc{Dijkstra}$ 函数中，
会以顶点 $u$ 初始化所有节点的距离 $v.d$ 所以无需再重置，同时在该函
数中加入求从起始节点到每一点的最短路径 $path$，这只需在更新 $v.d$ 时
作处理即可，分析最坏时间复杂度为 $O(|E|(|E|+|V|\lg|V|))$.

\begin{algorithm}[ht]
    \caption{求有向图中经过某点的最小环}\label{algo:3.2}
    \KwIn{不存在反向平行边的有向图 $G=(V,E)$ 的邻接表 $adj[1..n]$ 和边权函数 $w$，$n=|V|$，某点 $v$}
    \KwOut{最小环 $ansPath$ 及最小环的边权和 $ans$}
    $ans=\infty$\;
    \For{$u\in G.adj[v]$}{
        \textsc{Dijkstra} ($G,w,u$)\;
        \If{$w(v,u)+v.d<ans$}{
            $ans\leftarrow w(v,u)+v.d$\;
            $ansPath\leftarrow(v,u)\bigcup path(u,v)$}
    }
\end{algorithm}

(2.2) 相比算法~\ref{algo:3.2}，考虑在做 $\textsc{Dijkstra}$ 时，
传入的图从 $G$ 改为 $G'=(V,E\setminus\{(u,v)\})$，即假如存在一条
$(v,u)$ 的反向平行边，则不考虑该反向平行边，时间复杂度保持不变，仍为
$O(|E|(|E|+|V|\lg|V|))$.

(3) 见算法~\ref{algo:3.3}，因为使用的是深度优先搜索，所以时间复杂度为
$O(|E|)=O(|V|+k)$ 为线性最坏时间复杂度.

\begin{algorithm}[ht]
    \caption{求无向图的全局最小环}\label{algo:3.3}
    \KwIn{无向图 $G=(V,E)$ 的邻接表 $adj[1..n]$ 和边权函数 $w$，$n=|V|$}
    \KwOut{最小环 $ansPath$ 及最小环的边权和 $ans$}
    \SetKwProg{Fn}{Function}{:}{end}
    \SetKwFunction{Se}{DFS}

    $ans\leftarrow\infty$\;
    $ansPath\leftarrow\varnothing$\;
    $visited[1..n]\leftarrow\{False\}$\;
    $dis[1..n]\leftarrow\{\infty\}$\;
    $dis[1]\leftarrow0$\;
    $path[1..n]\leftarrow\{\varnothing\}$\;
    $temp\leftarrow1$\;
    \Se{$1$}\;

    \Fn{\Se{$u$}}{
    $visited[u]\leftarrow True$\;
    \For{$v\in G.adj[u]$}{
    \If{$v=parent[u]$}{
    continue\;
    }
    \If{$visited[v]$}{
    \If{$dis[u]-dis[temp]+dis[v]-dis[temp]+w(u,v)<ans$}{
    $ans\leftarrow dis[u]-dis[temp]+dis[v]-dis[temp]+w(u,v)$\;
    $ansPath\leftarrow (path[u]\setminus path[temp])\bigcup(path[v]\setminus path[temp])\bigcup\{(u,v)\}$\;
    }
    }
    \Else{
        $parent[v]\leftarrow u$\;
        $dis[v]\leftarrow dis[u]+w(u,v)$\;
        $path[v]\leftarrow path[u]\bigcup\{(u,v)\}$\;
        $orig\leftarrow temp$\;
        $temp\leftarrow u$\;
        \Se{$v$}\;
        $temp\leftarrow orig$\;
    }
    }
    }
\end{algorithm}

\hrulefill\medskip

\textbf{Q4.}

(1.1) $(x\lor y)\land(\neg y\lor z)\land(\neg z\lor \neg x)=(\neg x\to y)\land(\neg y\to x)\land(y\to z)\land(\neg z\to \neg y)\land(z\to\neg x)\land(x\to\neg z)$

转化为有向图即图~\ref{fig:4.1.1}

\begin{figure}[h]
    \centering
    \begin{tikzpicture}[->,>=stealth]
        \node[draw, circle] (1) at (0,0) {$x$};
        \node[draw, circle] (2) at (5,0) {$\neg x$};
        \node[draw, circle] (3) at (0,-3) {$y$};
        \node[draw, circle] (4) at (5,-3) {$\neg y$};
        \node[draw, circle] (5) at (0,-6) {$z$};
        \node[draw, circle] (6) at (5,-6) {$\neg z$};

        \draw[->]
        (1) edge node {} (6)
        (2) edge node {} (3)
        (3) edge node {} (5)
        (4) edge node {} (1)
        (5) edge node {} (2)
        (6) edge node {} (4);
    \end{tikzpicture}
    \caption{Q4.1.1}\label{fig:4.1.1}
\end{figure}

(1.2.1)

\begin{proof}
    假如 $\exists p$,top$[p]=$top$[\neg p]$，则 $p$ 和 $\neg p$
    位于同一个强连通分量中，因此 $p$ 和 $\neg p$ 可以互相到达，因此
    $p$ 和 $\neg p$ 可以同时取值为真，而这是不可能的，因此原公式
    不可满足.
\end{proof}

(1.2.2) 从拓扑排序最后一个强连通分量往回遍历，遍历每个强连通分量中的
变量，如果该变量还未被赋值，就赋值为真，并同时将该变量的否定赋值为假，
直到所有强连通分量被处理完.

\begin{proof}
    首先要让该式为真，需要每个强连通分量为真，而每个强连通分量，都是
    一系列蕴含式的合取，因此要么整个强连通分量上变量同时为真，要么
    整个强连通分量上变量同时为假.

    因为 $\forall p$,top$[p]\neq$top$[\neg p]$，所以 $p$ 和 $\neg p$
    不会同时出现在一个强连通分量中，因此对某个变量 $p$，其所在强连通
    分量和其否定 $\neg p$ 所在强连通分量之间，要么不存在边，此时是
    平凡的情况，随意赋值即可；要么只能从一方到另一方，此时后者的拓扑
    排序会更高，令后者为真，前者为假，则可以保证蕴含式为真.
\end{proof}

(2.1)见图~\ref{fig:4.2.1}

\begin{figure}[h]
    \centering
    \begin{tikzpicture}
        \node[draw, circle] (1) at (0,0) {$\neg x$};
        \node[draw, circle] (2) at (5,-1) {$y$};
        \node[draw, circle] (3) at (10,0) {$z$};
        \node[draw, circle] (4) at (0,-3) {$x$};
        \node[draw, circle] (5) at (5,-4) {$\neg y$};
        \node[draw, circle] (6) at (10,-3) {$z$};
        \node[draw, circle] (7) at (0,-6) {$\neg x$};
        \node[draw, circle] (8) at (5,-7) {$y$};
        \node[draw, circle] (9) at (10,-6) {$\neg z$};

        \draw
        (1) -- (2) -- (3) -- (1)
        (4) -- (5) -- (6) -- (4)
        (7) -- (8) -- (9) -- (7)
        (1) -- (4) -- (7)
        (2) -- (5) -- (8)
        (6) -- (9)
        (3) edge [bend left] (9);
    \end{tikzpicture}
    \caption{Q4.2.1}\label{fig:4.2.1}
\end{figure}

(2.2) 取图上的 $x$ 和两个 $y$ 即可，也就是 $x$ 和 $y$ 取值为真时，原表达式取值为真.

\end{document}