Graph Theory Quiz

Question 1

What is a graph?

A graph is a collection of points, called vertices, and lines connecting them, called edges. Graphs are used to represent relationships between different objects or ideas.

Question 2

What is the degree of a vertex?

The degree of a vertex is the number of edges connected to it. For example, if a vertex has three edges connected to it, then its degree is three.

Question 3

What is an edge in a graph?

An edge in a graph is a line connecting two vertices. It is used to represent a relationship between the two vertices.

Question 4

What is an isolated vertex?

An isolated vertex is a vertex that is not connected to any other vertices in the graph. It has no edges connected to it.

Question 5

What is the difference between a directed and an undirected graph?

A directed graph has edges with a direction, meaning that the edges are one-way. An undirected graph has edges without a direction, meaning that the edges are two-way.

Graph Theory Practice Sheet

Introduction

Graph theory is a branch of mathematics that studies the relationships between points, or vertices, and lines, or edges. Graph theory is used to model and analyze networks, such as social networks, transportation networks, and communication networks.

Basic Concepts

In graph theory, a graph is a collection of vertices and edges. A vertex is a point, and an edge is a line connecting two vertices. A graph can be directed or undirected. In a directed graph, the edges have a direction, while in an undirected graph, the edges do not have a direction.

Representing Graphs

Graphs can be represented in different ways. The most common way to represent a graph is with an adjacency matrix. In an adjacency matrix, the rows and columns represent the vertices, and the elements in the matrix represent the edges. If there is an edge between two vertices, the corresponding element in the matrix is set to 1, and if there is no edge between two vertices, the corresponding element in the matrix is set to 0.

Paths and Cycles

In graph theory, a path is a sequence of vertices connected by edges. A cycle is a path that starts and ends at the same vertex. In a directed graph, a path is called a directed path, and a cycle is called a directed cycle.

Practice Problems

1. Draw a graph with 4 vertices and 4 edges.

2. Draw a directed graph with 3 vertices and 3 edges.

3. Represent the following graph with an adjacency matrix:

A--B--C

1. Find a path from vertex A to vertex C in the following graph:

A--B--C--D

1. Find a cycle in the following graph:

A--B--C--A

1. Find a directed path from vertex A to vertex C in the following graph:

A-->B-->C