Exercise 1
problem
![[Pasted image 20260410132255.png]]
answer
![[7e33f0eec76a45bcc075b6fb9729f2be_720.jpg|653]]
Exercise 2
problem
![[Pasted image 20260410132628.png]]
answer
![[041cb6eaf76df1402464671253e5bf57_720.jpg]]
Exercise 3
problem
![[Pasted image 20260410132733.png]]
answer
(a)
Check if an undirected graph is bipartite
Require: Undirected graph $G = (V, E)$
Ensure: true if $G$ is bipartite, otherwise false
Initialize $\textit{color}[v] \gets -1$ for all $v \in V$ ($-1$ means uncolored)
for each $v \in V$ do
if $\textit{color}[v] = -1$ then
$\textit{color}[v] \gets 0$
Initialize queue $Q$, enqueue $v$
while $Q$ is not empty do
$u \gets Q.\text{dequeue}()$
for each $w \in \text{adj}[u]$ do
if $\textit{color}[w] = -1$ then
$\textit{color}[w] \gets 1 - \textit{color}[u]$
$Q.\text{enqueue}(w)$
else
if $\textit{color}[w] = \textit{color}[u]$ then
return false
end if
end if
end for
end while
end if
end for
return true
每个顶点至多入队一次，每条边至多被检查两次，时间复杂度$(O(|V|+|E|))$，是线性的
(b)
"二分图 $\implies$ 无奇环"：
运用反证法。
若存在奇环，我们对这个奇环进行染色，从任意一个点开始。按0101的顺序染色。
由于环上有奇数个节点，则首部与尾部一定是1个颜色，与二分图的定义矛盾
则二分图一定无奇环。
"无奇环 $\implies$ 二分图":
我们任取一点$s$，对任意一点$v$，记$d[v]$为$s$到$v$的最短路径。
将图中顶点分成两个集合：
若存在边$(u,v)$连接$A$中两点，则 $s\to u\to v\to s$ 构成一个长度为 $d[u]+d[v]+1$的奇环。矛盾。 同理$B$中任意两点间也无相邻顶点。
即证。
(c)
(应为at least?)
3种
从这个奇环中任意删去一条边，剩下的是2分图，可以用2种颜色染色，再补上这条边。由于奇环至少要3种颜色染色，故3种颜色即可。
Exercise 4
problem
![[Pasted image 20260410132756.png]]
answer
(a)
Compute the reverse graph in linear time
Require: Directed graph $G = (V, E)$ represented by adjacency lists
Ensure: Reverse graph $G^R = (V, E^R)$ where $E^R = \{(v,u) \mid (u,v) \in E\}$
Initialize an empty adjacency list $adjR[v]$ for each $v \in V$
for each vertex $u \in V$ do
for each vertex $v$ in $adj[u]$ do
Add $u$ to $adjR[v]$
end for
end for
return $G^R$ with adjacency lists $adjR$
每条边遍历一遍，时间复杂度$(O(|V|+|E|))$，是线性的
(b)
Order vertices by decreasing post values
Require: Directed graph $G = (V, E)$ represented by adjacency lists
Ensure: List $order$ containing vertices of $V$ sorted by decreasing post numbers
Initialize $visited[v] \gets \text{false}$ for all $v \in V$
Initialize empty list $postList$
function DFS($u$)
$visited[u] \gets \text{true}$
for each $v \in adj[u]$ do
if $\lnot visited[v]$ then
call DFS($v$)
end if
end for
Append $u$ to $postList$
end function
for each $v \in V$ do
if $\lnot visited[v]$ then
call DFS($v$)
end if
end for
$order \gets \text{reverse}(postList)$
return $order$
就单纯dfs一遍，时间复杂度$(O(|V|+|E|))$，是线性的