1. Problem: Find the in-degree and out-degree of each vertex in the given directed graphs. --- **Graph 1: Complete directed graph with 6 vertices (Team 1 to Team 6)** - In a complete directed graph with $n$ vertices and no self-loops, each vertex has edges to every other vertex. - Out-degree of each vertex = number of edges going out = $n-1 = 6-1 = 5$. - In-degree of each vertex = number of edges coming in = $n-1 = 5$. So for each Team 1 to Team 6: - In-degree = 5 - Out-degree = 5 --- **Graph 2: Tree structure with vertices main, display, parser, protocol, abstract syntax tree, page, network** - main points to display, parser, protocol - display points to abstract syntax tree - parser points to page - protocol points to network Calculate in-degree and out-degree: | Vertex | In-degree | Out-degree | |----------------------|-----------|------------| | main | 0 | 3 | | display | 1 | 1 | | parser | 1 | 1 | | protocol | 1 | 1 | | abstract syntax tree | 1 | 0 | | page | 1 | 0 | | network | 1 | 0 | --- **Graph 3: Rectangle with vertices Linda, Brian, Deborah, Fred, Yvonne and edges:** - Linda -> Brian - Linda -> Deborah - Deborah -> Fred - Fred -> Brian - Brian -> Fred - Brian -> Yvonne - Linda -> Fred - Fred -> Yvonne Calculate in-degree and out-degree: | Vertex | In-degree | Out-degree | |---------|-----------|------------| | Linda | 0 | 3 | (to Brian, Deborah, Fred) | Brian | 2 | 2 | (from Linda, Fred; to Fred, Yvonne) | Deborah | 1 | 1 | (from Linda; to Fred) | Fred | 3 | 2 | (from Deborah, Brian, Linda; to Brian, Yvonne) | Yvonne | 2 | 0 | (from Brian, Fred) --- Final answers: **Graph 1:** Each vertex has in-degree = 5, out-degree = 5. **Graph 2:** - main: in-degree 0, out-degree 3 - display: in-degree 1, out-degree 1 - parser: in-degree 1, out-degree 1 - protocol: in-degree 1, out-degree 1 - abstract syntax tree: in-degree 1, out-degree 0 - page: in-degree 1, out-degree 0 - network: in-degree 1, out-degree 0 **Graph 3:** - Linda: in-degree 0, out-degree 3 - Brian: in-degree 2, out-degree 2 - Deborah: in-degree 1, out-degree 1 - Fred: in-degree 3, out-degree 2 - Yvonne: in-degree 2, out-degree 0