Graph Theoruy

Question 1

Define a simple undirected graph

Answer 1

A non empty set V of vertices, nodes, and a set of undirected edges. Every edge has two distinct vertices, u and v, as endpoints.

Question 2

Define a directed graph

Answer 2

A non empty set V of vertices and a set of directed edges. Each directed edge has a start vertices u and an end vertex v.

Question 3

What is the degree of a vertex?

Answer 3

The number of edges connected to it

Question 4

What is the neighbourhood of a vertex?

Answer 4

The number of vertices connected to a vertex

Question 5

Handshaking Theorem

Answer 5

2m = SUM( Degrees of all the vertices )

Where m is the number of edges

Question 6

Define a complete graph

Answer 6

All possible edges exist (Complete graph with n nodes is denoted by Kn)

Question 7

Define a bipartite graph

Answer 7

Two distinct sets of nodes where no two nodes in the same set are directly connected by an edge

Question 8

Define a path

Answer 8

A series of nodes in a graph

Question 9

Define a cycle

Answer 9

A series of nodes in a graph with vertices v1 v2 … vk

Where v1 = vk and k > 2

Question 10

Define a tree

Answer 10

An undirected graph without a cycle

Question 11

Undirected graph theorem

Answer 11

THEOREM. Let G be an undirected graph on n nodes. Any two
of the following statements
I G is connected;
I G does not contain a cycle;
I G has n − 1 edges;
imply the third.

Question 12

What is an M-ary tree?

Answer 12

A rooted tree is called an m-ary tree if every node has at most m children

Question 13

Minimum spanning tree

Answer 13

A tree which connects all the nodes in a graph with the shortest weights possible

Question 14

Prim’s algorithm

Answer 14

Choose any vertex v1. Let T = {v1}. E = {}.
2. Choose the neighbour to v1 of least weight (nearest
neighbour) v2 and add to T. Add the edge from v1 to v2 to E.
3. Next add the nearest neighbour to T = {v1, v2}. This must
not create a cycle.
4. Stop when all vertices have been reached (and so
|E| = V − 1).