Strong Digraphs

• Read section 7.1, pages 161-168
• What is a digraph, arc, oriented graph?
• When do we say that a vertex \(u\) is adjacent to a vertex \(v\)? When do we say that it is adjacent from \(v\)?
• What are the indegree and outdegree of a vertex?
• What does the first theorem of digraph theory say?
• What is a directed walk/trail/path/circuit?
• When do we say that a directed graph is weakly connected?
• When do we say that a directed graph is strongly connected?
• Show examples of graphs that are weakly, but not strongly, connected.
• What is the directed distance from \(u\) to \(v\)? Is it a symmetric function?
• Why is it the case that if a digraph is strongly connected then each vertex has positive out- and in-degrees?
• Theorem 7.3: A digraph is strong if and only if it contains a closed spanning (directed) walk.
• What is an Eulerian Circuit? What is an Eulerian Graph?
• Theorem 7.4: A nontrivial connected digraph is Eulerian if and only if on each vertex the outdegree equals the indegree.
• What is an orientation for a nontrivial connected graph?
• Theorem 7.5: A nontrivial connected graph \(G\) has a strong orientation if and only if it contains no bridges.
• Practice problems: 7.2, 7.3, 7.4