path: root/2.3.4.2.lyx

#LyX 2.4 created this file. For more info see https://www.lyx.org/
\lyxformat 620
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\input defs
\end_preamble
\use_default_options true
\maintain_unincluded_children no
\language english
\language_package default
\inputencoding utf8
\fontencoding auto
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_roman_osf false
\font_sans_osf false
\font_typewriter_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement class
\float_alignment class
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_formatted_ref 0
\use_minted 0
\use_lineno 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tablestyle default
\tracking_changes false
\output_changes false
\change_bars false
\postpone_fragile_content false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\docbook_table_output 0
\docbook_mathml_prefix 1
\end_header

\begin_body

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc4[M20]
\end_layout

\end_inset

The concept of 
\emph on
topological sorting
\emph default
 can be defined for any finite directed graph 
\begin_inset Formula $G$
\end_inset

 as a linear arrangement of the vertices 
\begin_inset Formula $V_{1}V_{2}\dots V_{n}$
\end_inset

 such that 
\begin_inset Formula $\text{init}(e)$
\end_inset

 precedes 
\begin_inset Formula $\text{fin}(e)$
\end_inset

 in the ordering for all arcs 
\begin_inset Formula $e$
\end_inset

 of 
\begin_inset Formula $G$
\end_inset

.
 (See Section 2.2.3,
 Figs.
 6 and 7.) Not all finite directed graphs can be topologically sorted;
 which ones can be?
 (Use the terminology of this section to give the answer.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Only the ones with no directed cycles,
 except possibly for cycles of length 1.
 If 
\begin_inset Formula $G$
\end_inset

 has a cycle (of length 2 or more),
 the nodes in the cycle cannot be topologically ordered;
 otherwise the transitive closure of the edges of the graph is a partial ordering between the vertices,
 so they can be topologically ordered.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc7[M22]
\end_layout

\end_inset

True or false:
 A directed graph satisfying properties (a) and (b) of the definition of oriented tree,
 and having no oriented cycles,
 is an oriented tree.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

True for finite graphs.
 If there were cycles,
 they would be oriented because no vertex is the initial vertex of two arcs,
 and a graph with no cycles and exactly one edge less than the number of vertices is a free tree.
 Then the way to orient the edges such that (a) and (b) follow is unique,
 which can be proved by induction on the distance of a node to the root,
 and we know that this way follows (c).
\end_layout

\begin_layout Standard
False for infinite graphs.
 A graph whose vertices are 
\begin_inset Formula $R,V_{1},V_{2},\dots,V_{n},\dots$
\end_inset

 and whose edges are 
\begin_inset Formula $V_{1}\to V_{2}\to V_{3}\to\dots$
\end_inset

 follows (a) and (b) and has no cycles but it doesn't follow (c).
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc13[M24]
\end_layout

\end_inset

Prove that if 
\begin_inset Formula $R$
\end_inset

 is a root of a (possibly infinite) directed graph 
\begin_inset Formula $G$
\end_inset

,
 then 
\begin_inset Formula $G$
\end_inset

 contains an oriented subtree with the same vertices as 
\begin_inset Formula $G$
\end_inset

 and with root 
\begin_inset Formula $R$
\end_inset

.
 (As a consequence,
 it is always possible to choose the free subtree in flow charts like Fig.
 32 of Section 2.3.4.1 so that it is actually an 
\emph on
oriented
\emph default
 subtree;
 this would be the case in that diagram if we had selected 
\begin_inset Formula $e''_{13}$
\end_inset

,
 
\begin_inset Formula $e''_{19}$
\end_inset

,
 
\begin_inset Formula $e_{20}$
\end_inset

,
 and 
\begin_inset Formula $e_{17}$
\end_inset

 instead of 
\begin_inset Formula $e'_{13}$
\end_inset

,
 
\begin_inset Formula $e'_{19}$
\end_inset

,
 
\begin_inset Formula $e_{23}$
\end_inset

,
 and 
\begin_inset Formula $e_{15}$
\end_inset

.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We prove by induction that there is a family of oriented subtrees 
\begin_inset Formula $\{T_{n}\}_{n\geq0}$
\end_inset

 of 
\begin_inset Formula $G$
\end_inset

 with root 
\begin_inset Formula $R$
\end_inset

 such that 
\begin_inset Formula $T_{n}$
\end_inset

 contains exactly all the vertices 
\begin_inset Formula $V$
\end_inset

 in 
\begin_inset Formula $G$
\end_inset

 such that there is an oriented path from 
\begin_inset Formula $V$
\end_inset

 to 
\begin_inset Formula $R$
\end_inset

 of length at most 
\begin_inset Formula $n$
\end_inset

 and,
 furthermore,
 
\begin_inset Formula $T_{n-1}\subseteq T_{n}$
\end_inset

 for every 
\begin_inset Formula $n\geq1$
\end_inset

.
 It is easy to check that the union of this family of trees is a tree with all the vertices in 
\begin_inset Formula $G$
\end_inset

.
\end_layout

\begin_layout Standard
For 
\begin_inset Formula $n=0$
\end_inset

,
 we just take the trivial oriented tree,
 which only contains 
\begin_inset Formula $R$
\end_inset

.
 For 
\begin_inset Formula $n\geq1$
\end_inset

,
 and for every node 
\begin_inset Formula $V$
\end_inset

 such that the shortest oriented path from 
\begin_inset Formula $V$
\end_inset

 to 
\begin_inset Formula $R$
\end_inset

 has length 
\begin_inset Formula $n$
\end_inset

,
 we choose one such path 
\begin_inset Formula $VV_{1}\cdots V_{n-1}R$
\end_inset

,
 which we can do for all such vertices because of the axiom of choice.
 Since 
\begin_inset Formula $V_{1}$
\end_inset

 is in 
\begin_inset Formula $T_{n-1}$
\end_inset

,
 we just have to add 
\begin_inset Formula $V$
\end_inset

 and the arc 
\begin_inset Formula $(V,V_{1})$
\end_inset

 to 
\begin_inset Formula $T_{n-1}$
\end_inset

,
 for all such 
\begin_inset Formula $V$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
TODO 16,
 24
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc16[M24]
\end_layout

\end_inset

In a popular solitaire game called 
\begin_inset Quotes eld
\end_inset

clock,
\begin_inset Quotes erd
\end_inset

 the 52 cards of an ordinary deck of playing cards are dealt face down into 13 piles of four each;
 12 piles are arranged in a circle like the 12 hours of a clock and the thirteenth pile goes in the center.
 The solitaire game now proceeds by turning up the top card of the center pile,
 and then if its face value is 
\begin_inset Formula $k$
\end_inset

,
 by placing it next to the 
\begin_inset Formula $k$
\end_inset

th pile.
 (The numbers 
\begin_inset Formula $1,2,\dots,13$
\end_inset

 are equivalent to 
\begin_inset Formula $\text{A},2,\dots,10,\text{J},\text{Q},\text{K}$
\end_inset

.) Play continues by turning up the top card of the 
\begin_inset Formula $k$
\end_inset

th pile and putting it next to 
\emph on
its
\emph default
 pile,
 etc.,
 until we reach a point where we cannot continue since there are no more cards to turn up on the designated pile.
 (The player has no choice in the game,
 since the rules completely specify what to do.) The game is won if all cards are face up when the play terminates.
\end_layout

\begin_layout Standard
Show that the game will be won if and only if the following directed graph is an oriented tree:
 The vertices are 
\begin_inset Formula $V_{1},V_{2},\dots,V_{13}$
\end_inset

;
 the arcs are 
\begin_inset Formula $e_{1},e_{2},\dots,e_{12}$
\end_inset

,
 where 
\begin_inset Formula $e_{j}$
\end_inset

 goes from 
\begin_inset Formula $V_{j}$
\end_inset

 to 
\begin_inset Formula $V_{k}$
\end_inset

 if 
\begin_inset Formula $k$
\end_inset

 is the 
\emph on
bottom
\emph default
 card in pile 
\begin_inset Formula $j$
\end_inset

 after the deal.
\end_layout

\begin_layout Standard
(In particular,
 if the bottom card of pile 
\begin_inset Formula $j$
\end_inset

 is a 
\begin_inset Quotes eld
\end_inset


\begin_inset Formula $j$
\end_inset


\begin_inset Quotes erd
\end_inset

,
 for 
\begin_inset Formula $j\neq13$
\end_inset

,
 it is easy to see that the game is certainly lost,
 since this card could never be turned up.
 The result proved in this exercise gives a much faster way to play the game!)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

First we note that this graph already follows conditions (a) and (b) of the definition of an oriented tree,
 so it will be a tree if an only if 
\begin_inset Formula $V_{13}$
\end_inset

 is a root,
 if and only if there are no cycles (see Exercise 7).
 We also note that,
 since there are only 4 cards of each denomination,
 and we only take a card from a pile when we find its denomination except from one from 
\begin_inset Formula $V_{13}$
\end_inset

 at the start of the game,
 the only case where we cannot continue is after finding the last card with face value K.
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\implies]$
\end_inset


\end_layout

\end_inset

Assume that the game is not an oriented tree,
 then there is a cycle 
\begin_inset Formula $V_{k_{1}}\cdots V_{k_{m}}$
\end_inset

.
 We can assume that the 
\begin_inset Formula $k_{1}$
\end_inset

th pile is the first whose bottom card we turn up.
 Since clearly 
\begin_inset Formula $k_{1}\neq13$
\end_inset

,
 this means that we had already turned up all cards with denomination 
\begin_inset Formula $k_{1}$
\end_inset

,
 but we had not turned up 
\begin_inset Formula $k_{m}\#$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\impliedby]$
\end_inset


\end_layout

\end_inset

Assume we lost 
\begin_inset CommandInset href
LatexCommand href
name "the game"
target "https://en.wikipedia.org/wiki/The_Game_(mind_game)"
literal "false"

\end_inset

,
 which means that we have turned up all the cards with face value 13 and that,
 furthermore,
 we have turned up as many cards from the 
\begin_inset Formula $k$
\end_inset

th pile as cards with face value 
\begin_inset Formula $k$
\end_inset

.
 This means that,
 if
\begin_inset Formula 
\[
U\coloneqq\{V_{j}\mid\text{the }j\text{th pile's bottom card is down}\},
\]

\end_inset

then 
\begin_inset Formula $V_{13}\notin U$
\end_inset

 and each vertex of 
\begin_inset Formula $U$
\end_inset

 has one outgoing edge that points to another vertex in 
\begin_inset Formula $U$
\end_inset

,
 as we have already turned up all the cards with face value 
\begin_inset Formula $k$
\end_inset

 for 
\begin_inset Formula $V_{k}\notin U$
\end_inset

.
 Thus 
\begin_inset Formula $V_{13}$
\end_inset

 is not a root.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc24[M20]
\end_layout

\end_inset

Let 
\begin_inset Formula $G$
\end_inset

 be a connected digraph with arcs 
\begin_inset Formula $e_{0},e_{1},\dots,e_{m}$
\end_inset

.
 Let 
\begin_inset Formula $E_{0},E_{1},\dots,E_{m}$
\end_inset

 be a set of positive integers that satisfy Kirchhoff's law for 
\begin_inset Formula $G$
\end_inset

;
 that is,
 for each vertex 
\begin_inset Formula $V$
\end_inset

,
\begin_inset Formula 
\[
\sum_{\text{init}(e_{j})=V}E_{j}=\sum_{\text{fin}(e_{j})=V}E_{j}.
\]

\end_inset

Assume further that 
\begin_inset Formula $E_{0}=1$
\end_inset

.
 Prove that there is an oriented walk in 
\begin_inset Formula $G$
\end_inset

 from 
\begin_inset Formula $\text{init}(e_{0})$
\end_inset

 such that edge 
\begin_inset Formula $e_{j}$
\end_inset

 appears exactly 
\begin_inset Formula $E_{j}$
\end_inset

 times,
 for 
\begin_inset Formula $1\leq j\leq m$
\end_inset

,
 while edge 
\begin_inset Formula $e_{0}$
\end_inset

 does not appear.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We apply Theorem G to the graph whose vertices are those of 
\begin_inset Formula $G$
\end_inset

 and whose edges are the 
\begin_inset Formula $e_{j}$
\end_inset

 repeated 
\begin_inset Formula $E_{j}$
\end_inset

 times.
 This is valid,
 since we could as well place an intermediate vertex among each edge to avoid repeating edges,
 and it would give us an Eulerian cycle in that graph that goes through 
\begin_inset Formula $e_{0}$
\end_inset

 once.
 Coalescing the repeated edges into one gives us back graph 
\begin_inset Formula $G$
\end_inset

 and a cycle though 
\begin_inset Formula $G$
\end_inset

 that goes though edge 
\begin_inset Formula $e_{j}$
\end_inset

 exactly 
\begin_inset Formula $E_{j}$
\end_inset

 times,
 and we just have to remove the only appearance of 
\begin_inset Formula $e_{0}$
\end_inset

.
\end_layout

\end_body
\end_document