Unit 4_ GRAPH THEORY

Graph Theory Basics Outline

1. Graphs Overview

  • 2Graph Structure:

    • A graph G consists of a non-empty set of nodes (vertices) V and a set of edges E.

    • Each edge connects either one or two vertices, known as endpoints.

  • Edge Types:

    • Self Loop: An edge connecting a vertex to itself.

    • Simple Graph: No loops and no multiple edges exist between the same set of vertices.

  • Graph Types:

    • Finite Graph: Contains a finite number of vertices.

    • Infinite Graph: Contains an infinite number of vertices.

  • Multigraphs: Can contain multiple edges between the same node pairs.

  • Pseudograph: Allows both loops and multiple edges.

  • Null Graph: No edges connecting any vertices.

2. Types of Graphs

2.1 Directed Graphs (Digraphs)

  • A directed graph consists of vertices V and directed edges E.

  • Each directed edge is represented as an ordered pair of vertices, indicating the direction.

  • Directed Multigraphs: Allow multiple directed edges from one vertex to another.

  • Mixed Graph: Contains both directed and undirected edges.

2.2 Undirected Graphs

  • Adjacency: Two vertices u and v are adjacent if there’s an edge connecting them.

  • Degree of Vertex: The degree is the number of edges connected to a vertex; loops count as two.

  • Isolated Vertex: A vertex with degree zero (no connections).

  • Pendant Vertex: A vertex with degree one (connected to only one edge).

3. Vertex Degree

  • Definitions:

    • Indegree: The number of incoming edges to a vertex.

    • Outdegree : The number of outgoing edges from a vertex.

  • Total Degree Calculation: For a vertex v - Total degree = Indegree + Outdegree.

  • Handshake Theorem: The sum of the degrees of all vertices equals twice the number of edges.

4. Complete and Cycle Graphs

4.1 Complete Graphs

  • A complete graph Kn has an edge between every pair of distinct vertices.

  • Number of edges in Kn: n(n-1)/2.

4.2 Cycle Graphs

  • A cycle graph Cn has n vertices connected in a closed loop. Each vertex has degree 2.

5. Regular Graphs

  • A regular graph has all vertices of the same degree.

  • Properties: In a k-regular graph with n vertices, there are n*k/2 edges.

6. Special Graph Structures

6.1 Wheel Graphs

  • A wheel graph is created by connecting a central vertex to all vertices of a cycle.

    • Notation: Wn for a wheel graph with n vertices.

6.2 Bipartite Graphs

  • A bipartite graph's vertices can be divided into two disjoint sets such that no edges connect vertices within the same set.

  • Complete Bipartite Graph: Denoted K(m,n), where every vertex in set V1 connects to every vertex in set V2.

7. Connectivity

7.1 Walks and Trails

  • Walk: A sequence of vertices and edges.

  • Open Walk: Starts and ends at different vertices.

  • Closed Walk: Starts and ends at the same vertex.

  • Trail: Walk without repeating edges.

8. Euler and Hamilton Paths

8.1 Euler Paths and Circuits

  • Euler Path: Visits every edge exactly once. Starts and ends at different vertices.

  • Euler Circuit: Starts and ends at the same vertex and visits every edge exactly once.

8.2 Hamilton Paths and Circuits

  • Hamilton Path: Visits every vertex exactly once.

  • Hamilton Circuit: A Hamilton Path that is also a circuit.

9. Planar Graphs

  • Plotted in a plane without edges crossing each other.

  • Euler's Formula: r - e + v = 2, where r is the number of regions, e is edges, and v is vertices.

10. Matching in Graphs

10.1 Matching Definitions

  • Perfect Matching: Matches all vertices in the graph without overlaps.

  • Maximal Matching: Cannot add more edges without creating overlaps.

11. Trees and Spanning Trees

  • Tree Definition: A connected graph with no cycles; contains exactly n-1 edges if there are n vertices.

  • Spanning Tree: A subgraph containing all vertices and is a tree.

  • Minimum Spanning Tree: A tree with the smallest sum of edge weights.

12. Algorithms for Minimum Spanning Trees

12.1 Prim's Algorithm

  • Start with a node, keep adding the lowest weight edge until all vertices are included.

12.2 Kruskal's Algorithm

  • Sort edges by weight, add each edge ensuring no cycles until all vertices are connected.

Graph Theory Basics Outline

  1. Graphs Overview

    • Graph Structure:A graph G consists of a non-empty set of nodes (vertices) V and a set of edges E. Each edge connects either one or two vertices, known as endpoints.

    • Edge Types:

      • Self Loop: An edge connecting a vertex to itself.

      • Simple Graph: No loops and no multiple edges exist between the same set of vertices.

    • Graph Types:

      • Finite Graph: Contains a finite number of vertices.

      • Infinite Graph: Contains an infinite number of vertices.

      • Multigraphs: Can contain multiple edges between the same node pairs.

      • Pseudograph: Allows both loops and multiple edges.

      • Null Graph: No edges connecting any vertices.

  2. Types of Graphs2.1 Directed Graphs (Digraphs)- A directed graph consists of vertices V and directed edges E. Each directed edge is represented as an ordered pair of vertices, indicating the direction.- Directed Multigraphs: Allow multiple directed edges from one vertex to another.- Mixed Graph: Contains both directed and undirected edges.2.2 Undirected Graphs- Adjacency: Two vertices u and v are adjacent if there’s an edge connecting them.- Degree of Vertex: The degree is the number of edges connected to a vertex; loops count as two.- Isolated Vertex: A vertex with degree zero (no connections).- Pendant Vertex: A vertex with degree one (connected to only one edge).

  3. Vertex Degree

    • Definitions:

      • Indegree: The number of incoming edges to a vertex.

      • Outdegree: The number of outgoing edges from a vertex.

      • Total Degree Calculation: For a vertex v - Total degree = Indegree + Outdegree.

      • Handshake Theorem: The sum of the degrees of all vertices equals twice the number of edges.

  4. Complete and Cycle Graphs4.1 Complete Graphs- A complete graph Kn has an edge between every pair of distinct vertices.- Number of edges in Kn: n(n-1)/2.4.2 Cycle Graphs- A cycle graph Cn has n vertices connected in a closed loop. Each vertex has degree 2.

  5. Regular Graphs

    • A regular graph has all vertices of the same degree.

    • Properties: In a k-regular graph with n vertices, there are n*k/2 edges.

  6. Special Graph Structures6.1 Wheel Graphs- A wheel graph is created by connecting a central vertex to all vertices of a cycle.- Notation: Wn for a wheel graph with n vertices.6.2 Bipartite Graphs- A bipartite graph's vertices can be divided into two disjoint sets such that no edges connect vertices within the same set.- Complete Bipartite Graph: Denoted K(m,n), where every vertex in set V1 connects to every vertex in set V2.

  7. Connectivity7.1 Walks and Trails- Walk: A sequence of vertices and edges.- Open Walk: Starts and ends at different vertices.- Closed Walk: Starts and ends at the same vertex.- Trail: Walk without repeating edges.

  8. Euler and Hamilton Paths8.1 Euler Paths and Circuits- Euler Path: Visits every edge exactly once. Starts and ends at different vertices.- Euler Circuit: Starts and ends at the same vertex and visits every edge exactly once.8.2 Hamilton Paths and Circuits- Hamilton Path: Visits every vertex exactly once.- Hamilton Circuit: A Hamilton Path that is also a circuit.

  9. Planar Graphs

    • Plotted in a plane without edges crossing each other.

    • Euler's Formula: r - e + v = 2, where r is the number of regions, e is edges, and v is vertices.

  10. Matching in Graphs10.1 Matching Definitions- Perfect Matching: Matches all vertices in the graph without overlaps.- Maximal Matching: Cannot add more edges without creating overlaps.

  11. Trees and Spanning Trees

    • Tree Definition: A connected graph with no cycles; contains exactly n-1 edges if there are n vertices.

    • Spanning Tree: A subgraph containing all vertices and is a tree.

    • Minimum Spanning Tree: A tree with the smallest sum of edge weights.

  12. Algorithms for Minimum Spanning Trees12.1 Prim's Algorithm- Start with a node, keep adding the lowest weight edge until all vertices are included.12.2 Kruskal's Algorithm- Sort edges by weight, add each edge ensuring no cycles until all vertices are connected.

Key Points of Graph Theory Basics

  1. Graph Structure: A graph consists of vertices (nodes) and edges connecting them.

    • Edge Types: Self Loops, Simple Graphs, Finite and Infinite Graphs, Multigraphs, Pseudographs, Null Graphs.

  2. Types of Graphs:

    • Directed Graphs: Have directed edges; can have directed multigraphs and mixed graphs.

    • Undirected Graphs: Include concepts of adjacency, vertex degree, isolated, and pendant vertices.

  3. Vertex Degree: Involves definitions of indegree, outdegree, and total degree. Handshake theorem relates total degree to edges.

  4. Complete and Cycle Graphs:

    • Complete graphs have edges between all distinct vertex pairs.

    • Cycle graphs connect vertices in a closed loop.

  5. Regular Graphs: All vertices share the same degree, affecting edge counts.

  6. Special Graph Structures:

    • Wheel graphs connect a central vertex to cycle vertices.

    • Bipartite graphs divide vertices into two disjoint sets, with complete forms connecting all set members.

  7. Connectivity: Concepts of walks, trails, open and closed walks.

  8. Euler and Hamilton Paths: Define paths and circuits based on visiting edges or vertices exactly once.

  9. Planar Graphs: Drawn in a plane without edge crossings; Euler's formula connects regions, edges, and vertices.

  10. Matching in Graphs: Defines perfect and maximal matching in terms of vertex connections.

  11. Trees and Spanning Trees: Trees are acyclic connected graphs, with spanning trees containing all vertices.

  12. Algorithms for Minimum Spanning Trees: Discusses Prim's and Kruskal's algorithms for finding minimum spanning trees.

Typically, examiners may ask questions from a chapter on graph theory in various formats. Questions could include:

  1. Definitions and Concepts: Define key terms such as directed graphs, undirected graphs, and complete graphs.

  2. Types of Graphs: Explain the differences between a multigraph and a pseudograph.

  3. Applications: Provide examples of where Euler paths could be applied in real-world scenarios.

  4. Calculations: Given a certain graph, calculate the total degree of a vertex or the number of edges in a complete graph.

  5. Algorithms: Explain how Prim's algorithm works for finding a minimum spanning tree, potentially providing a step-by-step solution to an example graph.

  6. Spanning Trees: Describe the characteristics of a minimum spanning tree and how it differs from a simple spanning tree.

Here are the multiple-choice questions (MCQs) related to Graph Theory Basics along with their answers:

  1. What is a graph?a) A collection of edges onlyb) A collection of vertices onlyc) A collection of vertices and edgesd) None of the aboveAnswer: c) A collection of vertices and edges

  2. Which type of graph allows multiple edges between the same pair of vertices?a) Simple Graphb) Multigraphc) Finite Graphd) PseudographAnswer: b) Multigraph

  3. In a directed graph, each edge is represented as:a) An unordered pair of verticesb) A single vertexc) An ordered pair of verticesd) A loopAnswer: c) An ordered pair of vertices

  4. What is the degree of a vertex?a) The number of edges connected to itb) The total number of vertices in the graphc) The number of loops onlyd) None of the aboveAnswer: a) The number of edges connected to it

  5. Which theorem states that the sum of the degrees of all vertices equals twice the number of edges?a) Euler’s Theoremb) Handshake Theoremc) Hamiltonian Theoremd) Graph Connectivity TheoremAnswer: b) Handshake Theorem

  6. A complete graph Kn has how many edges?a) nb) n(n-1)c) n(n-1)/2d) 2nAnswer: c) n(n-1)/2

  7. What defines a Hamiltonian Path?a) Visits every edge exactly onceb) Visits every vertex exactly oncec) Visits all vertices and edgesd) None of the aboveAnswer: b) Visits every vertex exactly once

  8. Which algorithm can be used to find a minimum spanning tree?a) Prim's Algorithmb) Dijkstra’s Algorithmc) Breadth-First Searchd) Depth-First SearchAnswer: a) Prim's Algorithm

  9. In a bipartite graph, vertices can be divided into how many disjoint sets?a) Oneb) Twoc) Threed) Any numberAnswer: b) Two

  10. What distinguishes a tree in graph theory?a) It contains cyclesb) It is disconnectedc) It contains n-1 edges if there are n verticesd) None of the aboveAnswer: c) It contains n-1 edges if there are n vertices

Here are 20 additional multiple-choice questions (MCQs) related to Graph Theory Basics along with their answers:

  1. What type of graph contains vertices with no edges? a) Complete Graphb) Null Graphc) Cycle Graphd) Regular GraphAnswer: b) Null Graph

  2. How many edges does a cycle graph Cn have? a) n-1b) nc) n+1d) 2nAnswer: b) n

  3. In a bipartite graph, if set V1 has m vertices and set V2 has n vertices, what is the maximum number of edges? a) m+nb) mnc) m*n-1d) m/nAnswer: b) mn

  4. What is the minimum degree of a vertex in a tree with n vertices? a) 0b) 1c) 2d) n-1Answer: b) 1

  5. A graph with all vertices of degree 3 is called: a) 2-regularb) 3-regularc) 4-regulard) Complete GraphAnswer: b) 3-regular

  6. What is the characteristic of an Euler Circuit? a) Visits all vertices exactly onceb) Visits all edges at least oncec) Starts and ends at the same vertexd) Both b and cAnswer: d) Both b and c

  7. In which type of graph can you not have a cycle? a) Directed Graphb) Undirected Graphc) Treed) MultigraphAnswer: c) Tree

  8. Which algorithm is efficient for finding the shortest path in a graph? a) Kruskal's Algorithmb) Depth-First Searchc) Prim's Algorithmd) Dijkstra's AlgorithmAnswer: d) Dijkstra's Algorithm

  9. What is a defining feature of a connected graph? a) It contains cyclesb) All vertices are reachable from any vertexc) It has exactly one vertexd) None of the aboveAnswer: b) All vertices are reachable from any vertex

  10. What does a graph's edge represent? a) A connection between nodesb) A node's degreec) A loopd) None of the aboveAnswer: a) A connection between nodes

  11. How many spanning trees can a complete graph Kn have? a) nb) n!c) n^(n-2)d) 2^(n-1)Answer: c) n^(n-2)

  12. Which property do all bipartite graphs share? a) Can be colored with one colorb) Each vertex can only connect to vertices in the opposite setc) Have cyclesd) None of the aboveAnswer: b) Each vertex can only connect to vertices in the opposite set

  13. A tree with n vertices has how many edges? a) nb) n-1c) n+1d) 2nAnswer: b) n-1

  14. The degree of an isolated vertex is: a) 1b) 0c) 2d) UndefinedAnswer: b) 0

  15. If a graph has an even degree of each vertex, what can be concluded? a) It must have an Euler Circuitb) It must have a Hamiltonian Pathc) It is acyclicd) None of the aboveAnswer: a) It must have an Euler Circuit

  16. Which is not a property of trees? a) Acyclicb) Connectedc) Contains at least one cycled) Contains n-1 edges if there are n verticesAnswer: c) Contains at least one cycle

  17. A graph that contains a self loop is classified as: a) Simple Graphb) Multigraphc) Pseudographd) Complete GraphAnswer: c) Pseudograph

  18. What does it mean for a graph to be planar? a) Its edges can be coloredb) It can be drawn on a plane without edges crossingc) It contains cyclesd) None of the aboveAnswer: b) It can be drawn on a plane without edges crossing

  19. Which of the following is true regarding directed graphs? a) Edges have no directionb) Edges can connect the same vertices multiple timesc) Directed edges can only have one directiond) Both b and cAnswer: d) Both b and c

  20. The Handshake Theorem is applicable to: a) Treesb) Complete Graphsc) Any undirected graphd) None of the aboveAnswer: c) Any undirected graph

Here are some multiple-choice questions related to Graph Theory Basics along with their answers:

  1. What is a graph?a) A collection of edges onlyb) A collection of vertices onlyc) A collection of vertices and edgesd) None of the aboveAnswer: c) A collection of vertices and edges

  2. Which type of graph allows multiple edges between the same pair of vertices?a) Simple Graphb) Multigraphc) Finite Graphd) PseudographAnswer: b) Multigraph

  3. In a directed graph, each edge is represented as:a) An unordered pair of verticesb) A single vertexc) An ordered pair of verticesd) A loopAnswer: c) An ordered pair of vertices

  4. What is the degree of a vertex?a) The number of edges connected to itb) The total number of vertices in the graphc) The number of loops onlyd) None of the aboveAnswer: a) The number of edges connected to it

  5. Which theorem states that the sum of the degrees of all vertices equals twice the number of edges?a) Euler’s Theoremb) Handshake Theoremc) Hamiltonian Theoremd) Graph Connectivity TheoremAnswer: b) Handshake Theorem

  6. A complete graph Kn has how many edges?a) nb) n(n-1)c) n(n-1)/2d) 2nAnswer: c) n(n-1)/2

  7. What defines a Hamiltonian Path?a) Visits every edge exactly onceb) Visits every vertex exactly oncec) Visits all vertices and edgesd) None of the aboveAnswer: b) Visits every vertex exactly once

  8. Which algorithm can be used to find a minimum spanning tree?a) Prim's Algorithmb) Dijkstra’s Algorithmc) Breadth-First Searchd) Depth-First SearchAnswer: a) Prim's Algorithm

  9. In a bipartite graph, vertices can be divided into how many disjoint sets?a) Oneb) Twoc) Threed) Any numberAnswer: b) Two

  10. What distinguishes a tree in graph theory?a) It contains cyclesb) It is disconnectedc) It contains n-1 edges if there are n verticesd) None of the aboveAnswer: c) It contains n-1 edges if there are n vertices.

Here are additional multiple-choice questions related to Graph Theory Basics, categorized by level of difficulty:

Easy Questions:

  1. What is the primary purpose of a graph in mathematics?a) To calculate averagesb) To represent relationshipsc) To determine distancesd) None of the aboveAnswer: b) To represent relationships

  2. How many vertices are in a null graph?a) 0b) 1c) 5d) Any numberAnswer: d) Any number

  3. In a simple graph, what is the maximum degree of a vertex?a) n-1b) nc) 1d) 0Answer: a) n-1

Medium Questions:

  1. Which of these graphs cannot have a cycle?a) Complete graphb) Pseudographc) Treed) Cycle graphAnswer: c) Tree

  2. What is the characteristic of a cycle graph Cn?a) It has no edgesb) It connects vertices in a closed loopc) All vertices have different degreesd) None of the aboveAnswer: b) It connects vertices in a closed loop

  3. If a directed graph has 5 vertices, what is the maximum number of edges?a) 4b) 10c) 20d) 25Answer: b) 10

Hard Questions:

  1. What property makes a graph bipartite?a) It can be formed from a cycleb) It has a maximum degree of twoc) Its vertices can be split into two sets with no edges connecting within the same setd) It has a self-loopAnswer: c) Its vertices can be split into two sets with no edges connecting within the same set

  2. How can the total number of edges in a k-regular graph with n vertices be calculated?a) nkb) nk/2c) k/nd) k+nAnswer: b) n*k/2

  3. In Euler's theorem for connected graphs, what is necessary for a graph to contain an Euler Circuit?a) All vertices must have odd degreeb) At least one vertex must have an even degreec) All vertices must have even degreed) There must be a cycleAnswer: c) All vertices must have even degree

  4. If a graph has a perfect matching, what does it imply about the number of vertices?a) The number of vertices is oddb) The number of vertices is evenc) The graph is connectedd) The graph has cyclesAnswer: b) The number of vertices is even

Feel free to use or adapt these

Here are 20 additional multiple-choice questions (MCQs) related to Graph Theory Basics along with their answers:

  1. What is a characteristic of a multigraph? a) It contains no loops b) It has unique edges between vertex pairs c) It allows multiple edges between the same vertices d) None of the aboveAnswer: c) It allows multiple edges between the same vertices

  2. In a tree, what is the maximum degree of any vertex? a) 1 b) n c) n-1 d) 2Answer: c) n-1

  3. What does a tree represent in graph theory? a) A cycle b) A disconnected graph c) An acyclic connected graph d) A multigraphAnswer: c) An acyclic connected graph

  4. Which property must a bipartite graph satisfy? a) Contains cycles b) Vertices can be colored with only one color c) Vertices can only connect to vertices in the opposite set d) None of the aboveAnswer: c) Vertices can only connect to vertices in the opposite set

  5. Define a perfect matching in graph theory: a) Matches all vertices without overlaps b) Matches some vertices with overlaps c) Matches vertices randomly d) Matches only one vertex

  6. Answer: a) Matches all vertices without overlaps

  7. What defines a connected component in a graph? a) A subgraph containing no edges b) A subset of vertices where all vertices are reachable from each other c) A group of isolated vertices d) A single vertex

  8. Answer: b) A subset of vertices where all vertices are reachable from each other

  9. If all vertices in a graph have odd degrees, what can be inferred? a) The graph is connected b) The graph cannot have an Euler circuit c) The number of vertices is even d) The graph has all even edges

  10. Answer: b) The graph cannot have an Euler circuit

  11. How many edges in a tree with n vertices? a) n-1 b) n c) 2n d) n+1Answer: a) n-1

  12. Which concept explains the relationship between regions, edges, and vertices in planar graphs? a) Handshake Theorem b) Hamiltonian Path c) Euler's Formula d) Graph Connectivity Theorem

  13. Answer: c) Euler's Formula

  14. What does it mean for a graph to be directed? a) Edges have no specific direction b) All edges are one-way c) It has cycles d) All vertices are distinct

  15. Answer: b) All edges are one-way

  16. How would you describe a pseudograph? a) A graph with disconnected components b) A graph with multiple edges and loops c) A graph with no loops d) A complete graphAnswer: b) A graph with multiple edges and loops

  17. Which of the following is true for a Hamilton Circuit? a) Visits every edge exactly twice b) Visits every vertex exactly once and starts and ends at the same vertex c) Starts and ends at different vertices d) Visits at least one vertex twiceAnswer: b) Visits every vertex exactly once and starts and ends at the same vertex

  18. The total number of edges in a complete bipartite graph K(m,n) can be calculated as: a) m + n b) max(m, n) c) m * n d) m + n - 1Answer: c) m * n

  19. What is the result of removing an edge from a graph? a) It increases the degree of the vertices connected by that edge b) It cannot affect the connectedness of the graph c) It may disconnect the graphd) It adds a cycleAnswer: c) It may disconnect the graph

  20. What defines an Eulerian graph? a) It cannot be connected b) Every vertex has an even degree c) It must contain a cycle d) It has a perfect matchingAnswer: b) Every vertex has an even degree

  21. When performing a depth-first search on a graph, what data structure is typically used? a) Queue b) Stack c) Array d) Linked ListAnswer: b) Stack

  22. In the context of graph theory, what is a dominating set? a) A set of vertices that connects all other vertices b) A set of edges with maximum weight c) A set of vertices such that every vertex is either in the set or adjacent to a vertex in the set d) A set of isolated vertices

  23. Answer: c) A set of vertices such that every vertex is either in the set or adjacent to a vertex in the set

  24. Which characteristic does an acyclic directed graph (DAG) possess? a) It contains cycles b) It can be traversed in reverse c) It has no directed cycles d) All vertices are connected

  25. Answer: c) It has no directed cycles

  26. In terms of connectivity, what is a bridge in a graph? a) An edge whose removal increases the number of connected components b) A cycle formed by two edges c) A vertex connecting multiple edges d) A self-loopAnswer: a) An edge whose removal increases the number of connected components

  27. What does it mean if a graph is k-regular? a) All vertices have a degree of k b) The graph has exactly k vertices c) The graph contains k edges d) The graph has k cyclesAnswer: a) All vertices have a degree of k