Quiz on Graph Theory

Multiple Choice

1. What is Graph Theory?

   • A) A branch of mathematics that studies the properties of graphs.
   • B) A branch of mathematics that studies the properties of shapes.
   • C) A branch of mathematics that studies the properties of numbers.
   • D) A branch of mathematics that studies the properties of equations.

2. What is the basic element of a graph?

   • A) Edges
   • B) Nodes
   • C) Points
   • D) Lines

3. What is the maximum number of edges that can be connected to a single vertex in a graph?

   • A) 1
   • B) 2
   • C) 3
   • D) Unlimited

True/False

1. Graphs are used to represent relationships between objects.

   • True

2. The edges in a graph can have weights.

   • True

3. A graph can have multiple connected components.

   • True

Fill-in-the-Blank

1. A graph is a collection of ________ and ________.

   • Nodes, edges

2. A graph is said to be ________ if there is a path between any two vertices.

   • Connected

3. The ________ of a graph is the number of edges connected to a vertex.

   • Degree

Short Answer

1. What is the difference between a directed and an undirected graph?
   • A directed graph is a graph in which the edges have a direction, while an undirected graph is a graph in which the edges do not have a direction. In a directed graph, the edges have a source and a destination, while in an undirected graph, the edges do not have a source or a destination.

.

Graph Theory Practice Sheet

Introduction

Graph theory is a branch of mathematics that studies the relationships between objects. It is used in a variety of fields, such as computer science, engineering, and physics. Graphs are used to represent networks of objects, such as roads, computer networks, and social networks.

In this practice sheet, we will be exploring the basics of graph theory. We will look at the different types of graphs, how to represent them, and how to solve problems using graphs.

What is a Graph?

A graph is a collection of objects, called nodes, which are connected by edges. The edges can be directed or undirected, meaning that the connection between the nodes can go in either direction.

A graph can be represented in two ways:

1. As a visual diagram, with nodes represented by circles and edges represented by lines connecting them.

2. As a set of equations, where each node is represented by a letter and the edges are represented by equations between the letters.

Types of Graphs

There are two main types of graphs: directed and undirected.

In a directed graph, the edges have a direction, meaning that the connection between the nodes can only go in one direction.

In an undirected graph, the edges do not have a direction, meaning that the connection between the nodes can go in either direction.

Graph Problems

Graph problems are problems that can be solved using graph theory.

For example, consider the following graph:

The goal is to find the shortest path from node A to node D.

In this problem, we can use graph theory to solve it. We can use the equations to represent the graph and then use algorithms to find the shortest path.

Practice Problem 1

Given the following graph:

Find the shortest path from node A to node D.

Answer: A -> B -> D

Practice Problem 2

Given the following graph:

Find the shortest path from node A to node F.

Answer: A -> B -> C -> E -> F